动态规划
- 思路：
- 最多可以完成两笔交易，因此任意一天结束后，会处于5种状态：
- 未进行任何操作；
- 只进行了一次买操作；
- 进行了一次买操作和一次卖操作；
- 再完成了一次交易之后，进行了一次买操作；
- 完成了两次交易；
- 第 1 种状态利润未发生变化，不记录其状态；
- 假设其他四种状态的最大利润分别是 buy1，sell1，buy2，sell2；
- 对应的状态转移方程：
- 第 i 天状态为 buy1 可以是：
- 第 i - 1 天是 buy1，第 i 天不操作，即 buy1'；
- 第 i 天进行买操作，第 i - 1 天未进行任何操作 -prices[i]；
- 则 buy1 = max(buy1', -prices[i])；
- 第 i 天状态是 sell1 可以是：
- 第 i - 1 天是 sell1，第 i 天不操作，即 sell1'；
- 第 i - 1 天是 buy1，第 i 天卖出，即 buy1' + prices[i]；
- 则 sell1 = max(sell1', buy1' + prices[i])；
- 第 i 天状态是 buy2 可以是：
- 第 i - 1 天是 buy2，第 i 天不操作，即 buy2'；
- 第 i - 1 天是 sell1，第 i 天买入，即 sell1' - prices[i]；
- 则 buy2 = max(buy2', sell1' - prices[i])；
- 第 i 天状态是 sell2 可以是：
- 第 i - 1 天是 sell2，第 i 天不操作，即 sell2'；
- 第 i - 1 天是 buy2，第 i 天卖出，即 buy2' + prices[i]；
- 则 sell2 = max(sell2', buy2' + prices[i])；
- 同一天买入卖出对收益不会产生影响，在状态转移时，可以直接根据第 i 天计算出的值进行状态转移；
- 边界条件第 0 天：
- buy1 = -prices[0]
- sell1 = 0
- buy2 = -prices[0]
- sell2 = 0
- 从 i = 1 开始进行动态规划，最终 sell2 的结果即为所求的最大收益；
class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();int buy1 = -prices[0];int sell1 = 0;int buy2 = -prices[0];int sell2 = 0;for (int i = 0; i < size; ++i) {buy1 = std::max(buy1, -prices[i]);sell1 = std::max(sell1, buy1 + prices[i]);buy2 = std::max(buy2, sell1 - prices[i]);sell2 = std::max(sell2, buy2 + prices[i]);}return sell2;}
};
