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

2024-01-09 00:09:08

动态规划

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

文章来源:https://blog.csdn.net/N_BenBird/article/details/135468196
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。