力扣123. 买卖股票的最佳时机 III

动态规划

• 思路：
  • 最多可以完成两笔交易，因此任意一天结束后，会处于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;
    }
};

代码007普通

打赏 收藏 海报 链接