[8,9,3,5,1,3]
4
第三天(股票价格=3)买进，第四天(股票价格=5)卖出，收益为2 第五天(股票价格=1)买进，第六天(股票价格=3)卖出，收益为2 总收益为4。
[9,8,4,1]
0
[1,2,8,3,8]
12
第一笔股票交易在第一天买进，第三天卖出；第二笔股票交易在第四天买进，第五天卖出；总收益为12。 因最多只可以同时持有一只股票，所以不能在第一天进行第一笔股票交易的买进操作，又在第二天进行第二笔股票交易的买进操作（此时第一笔股票交易还没卖出），最后两笔股票交易同时在第三天卖出，也即以上操作不满足题目要求。
总天数不大于200000。保证股票每一天的价格在[1,100]范围内。
int max(int a, int b){
if(a < b){
a = b;
}
return a;
}
int maxProfit(int* prices, int pricesLen ) {
int dp[pricesLen][5], maximum = 0;
dp[0][0] = 0, dp[0][2] = 0, dp[0][4] = 0;
//initialization
dp[0][1] = -prices[0], dp[0][3] = -prices[0];
for (int i = 1; i < pricesLen; i++) {
dp[i][0] = dp[i - 1][0];
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
if (dp[pricesLen - 1][2] > 0) {
maximum = max(dp[pricesLen - 1][2], dp[pricesLen - 1][4]);
}
return maximum;
} 建议去leetcode 123题搜 代码随想录，讲解的算比较容易懂了
int max(int a, int b){
return a>b?a:b;
}
int maxProfit(int* prices, int pricesLen ) {
// write code here
int dp[pricesLen][5];
for(int n=0;n<pricesLen;n++){
for(int j=0;j<5;j++){
dp[n][j] = -10001;
}
}
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i=1;i<pricesLen;i++){
dp[i][0] = dp[i-1][0];
dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]);
dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i]);
dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i]);
dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i]);
}
return max(0, max(dp[pricesLen-1][4],dp[pricesLen-1][2]));
} 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
