动态规划-买股票的最佳时机三

传送门

动态规划：用历史记录来避免重复计算，常用二维数组来记录历史

步骤：找到初始值，找到下一个结果和历史结果的关系并列出关系式

每天的操作有五种状态：

					 - 不操作
					 - 第一次买入
					 - 第一次卖出
					 - 第二次买入
					 - 第二次卖出
1
2
3
4
5

不操作无需更新状态
每天更新其余四个买卖状态的最大收益（第一次买入、第一次卖出、第二次买入、第二次卖出）
由于求最大收益，所以初始状态为第一天买入不卖出（既最小收益）。
最后返回完成两次交易的最大收益。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int buy1=-prices[0],sell1=0;
        int buy2=-prices[0],sell2=0;
        for(int i=1;i<n;i++){
            buy1=max(-prices[i],buy1);
            sell1=max(sell1,buy1+prices[i]);
            buy2=max(buy2,sell1-prices[i]);
            sell2=max(sell2,buy2+prices[i]);
        }
        return sell2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15