Cover image for Interview Classic 150 Questions P123 Best Time to Buy and Sell Stock III

Interview Classic 150 Questions P123 Best Time to Buy and Sell Stock III

(Updated: )
algorithm
, ,
Timeline

timeline

2025-12-17

init

dynamic programming

Title:

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, be careful not to use INT_MIN for initialization, as it will cause overflow in later calculations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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 purchase,
                // dp[i][1] means first buy completed,
                // dp[i][2] means first sell completed,
                // dp[i][3] means second buy completed,
                // dp[i][4] means second sell completed
                
                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, buy, or sell (only if you have already bought)
                for (i = 1; i < n; i++) {
                        // The previous state of not buying is not buying
                        dp[i][0] = dp[i - 1][0];

                        // The previous state of the first buy is not buying, either continue 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, either continue 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, either continue 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, either continue 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;
        }
};