政子的博客

技术|学习|随笔

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];
    }
};