Best Time to Buy and Sell Stock IV — At Most k Transactions 2D DP

Problem Statement#

You are given an integer array prices where prices[i] is the price of a given stock on the i-th day, and an integer k. Find the maximum profit you can achieve. You may complete at most k transactions: each transaction is one buy followed by one sell. Note: You may not engage in multiple transactions simultaneously.

Constraints:

• 1 <= k <= 100
• 1 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

Example 1:

Input:  k = 2, prices = [2, 4, 1]
Output: 2
Explanation: Buy on day 1 (price=2), sell on day 2 (price=4). Profit = 2.

Example 2:

Input:  k = 2, prices = [3, 2, 6, 5, 0, 3]
Output: 7
Explanation: Buy on day 2 (price=2), sell on day 3 (price=6). Profit = 4.
             Buy on day 5 (price=0), sell on day 6 (price=3). Profit = 3.
             Total = 7.

Example 3:

Input:  k = 1, prices = [1, 2]
Output: 1

Why This Problem Matters#

Stock IV (LC 188) is the apex of the stock problem series. It subsumes all prior variants:

• k=1: reduces to Stock I (LC 121)
• k=2: reduces to Stock III (LC 123)
• k >= n/2: equivalent to unlimited transactions (LC 122)

This is a Hard-level problem that Google and Meta commonly ask as the culminating challenge after warming up with Stock I and Stock III in the same interview round. It requires:

1. A 2D DP table where one dimension is the number of transactions used and the other is the day.
2. A shortcut for large k (when k >= len(prices) // 2, fall back to unlimited transactions).
3. Understanding optimal substructure across both the time dimension and the transaction dimension.

The Core Insight#

State definition: dp[t][0] = maximum profit using at most t transactions, not holding stock today dp[t][1] = maximum profit using at most t transactions, holding stock today

Transitions per day:

dp[t][0] = max(dp[t][0], dp[t][1] + price)   # sell today or rest
dp[t][1] = max(dp[t][1], dp[t-1][0] - price) # buy today using (t-1) transactions

Note: A "transaction" is counted when we buy. Using dp[t-1][0] in the buy transition ensures that the t-th buy is funded from a state with at most t-1 complete transactions.

Alternative: arrays of buy/sell states (simpler to code):

buy[t]  = max(buy[t],  sell[t-1] - price)  # t-th buy
sell[t] = max(sell[t], buy[t] + price)      # t-th sell

Initialize buy[0..k] = -infinity, sell[0..k] = 0. Update for all transactions in order each day.

Large k shortcut: If k >= len(prices) // 2, any profitable adjacent trade can be collected — use the Stock II greedy (sum all positive adjacent differences).

Answer: sell[k] (or dp[k][0]) after processing all days.

Building the DP Solution#

Step 1 — Large k shortcut:

def maxProfit(k, prices):
    n = len(prices)
    if k >= n // 2:
        # Unlimited transactions — greedy
        return sum(max(prices[i]-prices[i-1], 0) for i in range(1, n))

Step 2 — k-transaction state machine:

    buy  = [float('-inf')] * (k + 1)
    sell = [0] * (k + 1)
 
    for price in prices:
        for t in range(1, k + 1):
            buy[t]  = max(buy[t],  sell[t-1] - price)
            sell[t] = max(sell[t], buy[t] + price)
 
    return sell[k]

Update order within each day: Iterate t from 1 to k. Within each t, update buy[t] first (using previous day's sell[t-1]), then sell[t] (using the just-updated buy[t]).

Visual Dry Run#

Input: k = 2, prices = [3, 2, 6, 5, 0, 3]

Initialize: buy = [-inf, -inf, -inf], sell = [0, 0, 0]

Answer: sell[2] = 7

Optimized Solution#

Python#

class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        n = len(prices)
 
        # Shortcut: if k is large enough, behave like unlimited transactions
        if k >= n // 2:
            return sum(
                max(prices[i] - prices[i - 1], 0)
                for i in range(1, n)
            )
 
        # k-transaction state machine
        # buy[t] = best profit while holding after t-th buy
        # sell[t] = best profit while not holding after t-th complete transaction
        buy  = [float('-inf')] * (k + 1)
        sell = [0] * (k + 1)
 
        for price in prices:
            for t in range(1, k + 1):
                # Use sell[t-1] from the previous day (no same-day simultaneous transactions)
                buy[t]  = max(buy[t],  sell[t - 1] - price)
                sell[t] = max(sell[t], buy[t] + price)
 
        return sell[k]

JavaScript#

var maxProfit = function(k, prices) {
    const n = prices.length;
 
    // Unlimited transactions shortcut
    if (k >= Math.floor(n / 2)) {
        let profit = 0;
        for (let i = 1; i < n; i++) {
            profit += Math.max(prices[i] - prices[i - 1], 0);
        }
        return profit;
    }
 
    const buy  = new Array(k + 1).fill(-Infinity);
    const sell = new Array(k + 1).fill(0);
 
    for (const price of prices) {
        for (let t = 1; t <= k; t++) {
            buy[t]  = Math.max(buy[t],  sell[t - 1] - price);
            sell[t] = Math.max(sell[t], buy[t] + price);
        }
    }
 
    return sell[k];
};

Complexity Analysis#

For k <= n/2, the algorithm is O(n * k). For k > n/2, the shortcut makes it O(n).

Common Mistakes#

1. Not handling the large k case. When k >= n // 2, there are enough days to make any profitable trade — it degenerates to unlimited transactions. Without the shortcut, the O(n * k) loop runs for arbitrarily large k, potentially timing out.

2. Initializing buy[0] instead of leaving it at -infinity. buy[0] should remain -infinity (or not be used). There is no "0th buy" in the state machine — the 1st buy uses sell[0] = 0 (no prior transactions). Modifying buy[0] corrupts the chain.

3. Wrong inner loop order. The inner loop must go from t = 1 to k. For each t, buy[t] must use sell[t-1] from the PREVIOUS day. In the current implementation, since t increments, sell[t-1] was computed at the same day's t-1 iteration. This is actually correct behavior (same-day buy-sell chains are allowed), but confused candidates may try to separate the buy and sell updates into two separate passes — unnecessary.

4. Returning sell[k-1] or buy[k] instead of sell[k]. The answer is sell[k] — maximum profit after at most k complete transactions with no stock held. buy[k] means still holding after the k-th buy — unrealized profit.

5. Not recognizing that "at most k" includes fewer transactions. The state machine naturally handles using fewer than k transactions: if transactions 2 through k add no profit, sell[k] will equal sell[1] and the extra iterations contribute nothing.

Interview Tips#

• State the large-k shortcut immediately: "First I check: if k >= n//2, unlimited transactions are possible — I use the greedy approach." This signals you've seen the edge case.
• Connect to Stock III: "For k=2, this is exactly Stock III's 4-variable state machine. For general k, I just extend to buy[k] and sell[k] arrays."
• Explain sell[t-1] in the buy transition: "The t-th buy is funded from sell[t-1] — the state after completing t-1 transactions. This enforces the constraint that you must sell before buying again."
• Time complexity matters: "For k up to n/2, this is O(n*k). For larger k, the greedy shortcut keeps it O(n)." Interviewers at Google specifically look for this analysis.

Follow-up Questions#

Q: What if k is very large (k = 10^9)? For k >= n//2, any upward price movement can be captured — use the Stock II greedy: sum all positive adjacent differences in O(n).

Q: How does this simplify to Stock I (k=1)? With k=1: buy[1] = max(buy[1], sell[0] - price) = max(buy[1], -price). sell[1] = max(sell[1], buy[1] + price). This is exactly the Stock I state machine.

Q: What is the space-optimized approach? The current approach already uses O(k) space. The 2D DP approach uses O(n * k). For k << n, the state machine is already optimal. For k >> n, the shortcut gives O(1) space.

Q: Can you solve Stock IV with a different DP formulation? Yes: dp[t][i] = max profit using at most t transactions through day i. The recurrence is dp[t][i] = max(dp[t][i-1], max_{j<i}(prices[i] - prices[j] + dp[t-1][j-1])). This is O(n^2 * k) without optimization; the state machine reduces it to O(n * k).

Key Takeaways#

• For k >= n//2, use the Stock II greedy shortcut (sum all positive adjacent differences) — any profitable trade is capturable.
• For small k, use the state machine: buy[t] = max(buy[t], sell[t-1] - price) and sell[t] = max(sell[t], buy[t] + price) for t from 1 to k.
• Initialize buy = [-inf] * (k+1) and sell = [0] * (k+1).
• The answer is sell[k] after processing all prices.
• This generalizes Stock III (k=2) by simply extending the 4 state variables to 2k variables — mechanically trivial, conceptually the same state machine.
• Always check the large-k shortcut in an interview — it is a deliberate edge case that separates candidates who think about constraints from those who just code the core loop.