We tackle two classic stock trading problems: at most two transactions (LeetCode 123) and at most k transactions (LeetCode 188). Both problems prohibit holding more than one share at a time: you must sell before buying again.

Problem 123: Best Time to Buy and Sell Stock III

Given an array prices, find the maximum profit achievable by completing at most two transactions. A transaction is a buy followed by a sell.

Key Insight: Define five states for each day i:

• j = 0: no transaction
• j = 1: first buy (holding first stock)
• j = 2: first sell (not holding any stock after first sell)
• j = 3: second buy (holding second stock)
• j = 4: second sell (final state)

Let dp[i][j] be the maximum cash you have on day i in state j.

Recurrence:

• dp[i][0] = dp[i-1][0]
• dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
• dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
• dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])
• dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])

Initialization:

• Day 0: dp[0][0] = 0; dp[0][1] = -prices[0]; dp[0][2] = 0 (buy and sell same day); dp[0][3] = -prices[0]; dp[0][4] = 0.
• All other values default to 0.

Order of traversal: iterate from day 1 to n-1.

Final answer: dp[n-1][4].

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = dp[i-1][0];
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
            dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i]);
            dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i]);
            dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i]);
        }
        return dp.back()[4];
    }
};

Problem 188: Best Time to Buy and Sell Stock IV

Now we generalize to at most k transactions.

State representation: With k transactions, we have 2*k + 1 states:

• 0: no operation
• 1: first buy (odd)
• 2: first sell (even)
• 3: second buy
• 4: second sell
• ... up to 2*k: final sell.

Let dp[i][j] be maximum cash on day i in state j.

Recurrence patttern: For each transaction index t from 0 to k-1:

dp[i][2*t+1] = max(dp[i-1][2*t+1], dp[i-1][2*t] - prices[i]);
dp[i][2*t+2] = max(dp[i-1][2*t+2], dp[i-1][2*t+1] + prices[i]);

Initialization:

• dp[0][0] = 0.
• For all odd j (1,3,...,2k-1): dp[0][j] = -prices[0].
• All other states remain 0.

Final answer: dp[n-1][2*k].

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.empty() || k == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(2*k + 1, 0));
        for (int j = 1; j < 2*k; j += 2) {
            dp[0][j] = -prices[0];
        }
        for (int i = 1; i < prices.size(); ++i) {
            for (int t = 0; t < k; ++t) {
                int buy_idx  = 2*t + 1;
                int sell_idx = 2*t + 2;
                dp[i][buy_idx] = max(dp[i-1][buy_idx], dp[i-1][buy_idx-1] - prices[i]);
                dp[i][sell_idx] = max(dp[i-1][sell_idx], dp[i-1][buy_idx] + prices[i]);
            }
        }
        return dp.back()[2*k];
    }
};

Both solutions run in O(nk) time and O(nk) space, wich is optimal for this DP formulation.