题解 | #买卖股票的最好时机(一)#
买卖股票的最好时机(一)
http://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec
/*
动态规划：
0代表当前不持股的最大利益，1代表当前持股的最大利益
dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1],-prices[i]);
*/
int max(int a,int b){
if(a>b) return a;
else return b;
}
int maxProfit(int* prices, int pricesLen ) {
if(pricesLen==0) return 0;
int dp[pricesLen][2];
memset(dp,0,sizeof(dp));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1; i < pricesLen; i++){
dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1],-prices[i]);
}
return dp[pricesLen-1][0];
}
腾讯公司福利 864人发布
