面试经典150题 P123 买卖股票的最佳时机 III

---

时间轴

时间轴

2025-12-17

init

动态规划

---

题目：

P123 买卖股票的最佳时机 III

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/?envType=study-plan-v2&envId=top-interview-150

状态转移，注意初始化不要用 INT_MIN，会导致后面计算溢出

#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
        int maxProfit(vector<int> &prices)
        {
                int i, n = prices.size();
                int max_profit = 0;

                if (n == 1) {
                        return 0;
                }
                // dp[i][j]表示到第i天第j个状态的最大利润
                // dp[i][0]表示没有买入，
                // dp[i][1]表示已经第一次买入，
                // dp[i][2]表示第一次卖出，
                // dp[i][3]表示第二次买入，
                // dp[i][4]表示第二次卖出
                
                vector<vector<int> > dp(n, vector<int>(5, 0));
                dp[0][0] = 0;
                dp[0][1] = -prices[0];
                dp[0][2] = -1e9;
                dp[0][3] = -1e9;
                dp[0][4] = -1e9;

                // 每一天可以选择不买入，买入，或卖出（当且仅当已经买入过）
                for (i = 1; i < n; i++) {
                        // 没有买入的前一个状态是没有买入
                        dp[i][0] = dp[i - 1][0];

                        // 第一次买入的前一个状态是没有买入，沿用昨天状态或买入今天股票
                        dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

                        // 第一次卖出的前一个状态是第一次买入，沿用昨天状态或卖出今天股票
                        dp[i][2] = std::max(dp[i - 1][2], dp[i - 1][1] + prices[i]);

                        // 第二次买入的前一个状态是第一次卖出，沿用昨天状态或买入今天股票
                        dp[i][3] = std::max(dp[i - 1][3], dp[i - 1][2] - prices[i]);

                        // 第二次卖出的前一个状态是第二次买入，沿用昨天状态或卖出今天股票
                        dp[i][4] = std::max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

                        max_profit = std::max({ dp[i][0], dp[i][2], dp[i][4], max_profit });
                }
                return max_profit;
        }
};