AlgoMaster Logo

Best Time to Buy and Sell Stock IV

hardFrequencyUpdated September 21, 2026

Understanding the Problem

This is the generalized version of the stock trading problem: instead of one transaction or unlimited transactions, you get at most k. The transaction limit is what makes it hard.

You cannot pick the k most profitable price windows greedily, because the windows interact. With prices = [1, 5, 2, 6] and k = 2, the single most profitable trade is buying at 1 and selling at 6, for a profit of 5. But taking it leaves no room for a second trade, while two smaller trades, 1 to 5 and 2 to 6, total 8. Choosing one transaction changes which others are possible, so the choices cannot be made independently.

What can be made independent is the state. At any point in time, everything relevant is captured by three values: the current day, how many transactions we have started, and whether we are holding a stock. Two histories that agree on these three values have identical futures, which is the structure dynamic programming requires.

Key Constraints:

  • 1 <= prices.length <= 1000 --> Combined with k up to 100, there are at most 100,000 (day, transaction) pairs, so an O(n * k) DP runs well within limits.
  • 1 <= k <= 100 --> A transaction needs a buy day and a later sell day, so at most n/2 transactions fit in n days. When k >= n/2, the limit can never bind and the problem reduces to the unlimited-transactions case, which has an O(n) greedy solution.
  • 0 <= prices[i] <= 1000 --> Each transaction earns at most 1000 and at most 500 transactions fit in 1000 days, so the answer never exceeds 500,000. Standard 32-bit integers are safe.

Approach 1: Recursion with Memoization

Intuition

On each day, the available moves depend on whether we are holding a stock:

  • If we are NOT holding a stock: We can either buy today (if we have transactions remaining) or skip.
  • If we ARE holding a stock: We can either sell today or hold.

This decision tree branches at every day, but many branches converge. Day 5 with one transaction started and a stock in hand is the same situation regardless of which earlier days produced it, so its best future profit needs to be computed once and can be reused by every path that reaches it.

We define solve(day, txn, holding) as the maximum profit achievable from day day onward, where txn is the number of transactions started so far and holding indicates whether we currently own a stock. A buy increments the transaction count; the matching sell completes that transaction without incrementing it again.

Algorithm

  1. Define a recursive function solve(day, txn, holding) where day is the current day index, txn is the number of transactions started so far, and holding is 0 or 1.
  2. Base case: if day == n, return 0 (no more days to trade).
  3. If holding == 0 (not holding): max of skip (solve(day+1, txn, 0)) and buy if txn < k (-prices[day] + solve(day+1, txn+1, 1)).
  4. If holding == 1 (holding): max of hold (solve(day+1, txn, 1)) and sell (prices[day] + solve(day+1, txn, 0)).
  5. Memoize results in a 3D array memo[day][txn][holding].
  6. Return solve(0, 0, 0).

Visualization and Code

Loading animation...

Memoization achieves O(n k) time, but it stores the full O(n k) table and an O(n) recursion stack. The next approach computes the same states iteratively with O(k) memory.

Approach 2: 1D DP (Buy/Sell Arrays)

Intuition

The day dimension does not need to be stored. Processing prices one day at a time, we keep two running values for each transaction j (from 1 to k):

  • buy[j]: The maximum balance (profit so far minus purchase price) after buying stock for the j-th transaction.
  • sell[j]: The maximum profit after completing the j-th transaction (bought and sold).

On each day, for each transaction j:

  • buy[j] = max of keeping the old buy[j] (we already bought earlier) or buying today on top of the profit from j-1 completed transactions: sell[j-1] - prices[day].
  • sell[j] = max of keeping the old sell[j] (we already sold earlier) or selling today against the best buy for this transaction: buy[j] + prices[day].

The same recurrence can also be derived from a 2D table dp[j][i] (maximum profit using at most j transactions on days 0 through i): selling on day i means scanning every earlier buy day m for the best dp[m][j-1] - prices[m], an O(n^2 k) computation. Only the running maximum of that quantity is ever needed, and that running maximum is buy[j]. Carrying it forward day by day removes the inner scan and brings the time back to O(n k).

One special case remains. When k >= n/2, the transaction limit cannot bind (at most n/2 transactions fit in n days), and the answer is the unlimited-transactions profit: the sum of every day-over-day price rise. Each rise can be captured by its own buy-sell pair, and any single transaction's profit equals the sum of the daily changes it spans, which is at most the sum of the rises alone. The sum of rises is therefore both achievable and an upper bound.

Algorithm

  1. If k >= n/2, solve greedily: sum prices[i] - prices[i-1] for every day where the price went up. Return the sum.
  2. Initialize arrays buy[0..k] with -infinity (no buy has been made) and sell[0..k] with 0 (no profit from zero completed transactions).
  3. For each day i from 0 to n-1:
    • For each transaction j from 1 to k:
      • buy[j] = max(buy[j], sell[j-1] - prices[i])
      • sell[j] = max(sell[j], buy[j] + prices[i])
  4. Return sell[k].

Visualization and Code

Loading animation...