LeetCode-Best Time to Buy and Sell Stock III

思路想起来比较麻烦,不过还是 dp 的思想,之前的题目买股票的次数是不限制的,所以可以有 prices.size()次,但是现在受限制,就只能有 2 次了。所以 buy 和 sell 数组的大小都是 2。

首先,需要遍历每天的股票情况,然后根据每天的股票情况确定是第一次还是第二次,是买入还是卖出。具体的策略就是第一次买入和卖出一定要选当前最大的收益,第二次买入和卖出要在第一次最大收益的基础上获取更大的收益。

递推公式:

1
2
buy[j]=sell[j-1]-price[i]   if buy[j]<sell[j-1]+price[i]
sell[j]=buy[j]+price[i] if sell[j]<buy[j]+price[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int maxProfit(vector<int>& prices) {
int size=(int)prices.size();
int buy[2];
int sell[2];
buy[0]=INT_MIN;
buy[1]=INT_MIN;
sell[0]=0;
sell[1]=0;
for(int i=0;i<size;i++){
for(int j=0;j<2;j++){
if(buy[j]<(j>0?sell[j-1]:0)-prices[i]) buy[j]=(j>0?sell[j-1]:0)-prices[i];
if(sell[j]<buy[j]+prices[i]) sell[j]=buy[j]+prices[i];
}
}
return sell[1];
}
};