Interview Classic 150 Problem 123: Best Time to Buy and Sell Stock III

---

Timeline

Timeline

2025-12-17

init

Dynamic Programming

---

Problem:

P123 Best Time to Buy and Sell Stock III

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

State transition. Note: don’t use INT_MIN for initialization, as it will cause overflow in later calculations.

#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] represents the maximum profit up to day i in state j.
                // dp[i][0] means no stock bought,
                // dp[i][1] means the first buy has been made,
                // dp[i][2] means the first sell has been made,
                // dp[i][3] means the second buy has been made,
                // dp[i][4] means the second sell has been made
                
                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;

                // Each day you can choose not to buy, to buy, or to sell (only if you have already bought).
                for (i = 1; i < n; i++) {
                        // The previous state of 'no buy' is 'no buy'.
                        dp[i][0] = dp[i - 1][0];

                        // The previous state of the first buy is 'no buy'; carry over yesterday's state or buy today's stock.
                        dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

                        // The previous state of the first sell is the first buy; carry over yesterday's state or sell today's stock.
                        dp[i][2] = std::max(dp[i - 1][2], dp[i - 1][1] + prices[i]);

                        // The previous state of the second buy is the first sell; carry over yesterday's state or buy today's stock.
                        dp[i][3] = std::max(dp[i - 1][3], dp[i - 1][2] - prices[i]);

                        // The previous state of the second sell is the second buy; carry over yesterday's state or sell today's stock.
                        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;
        }
};