Stock / State Machine

At Most K Transactions

dp[k][i] = max profit using at most k transactions up to day i. For each day and each allowed transaction, choose: do nothing, or complete a transaction. Reduce space by noting dp[k] only depends on dp[k−1].

O(n * k)

How It Works

With at most k transactions, the state machine gains a transaction-count dimension. Define hold[j] as the best profit while owning a share during transaction j, and sell[j] as the best profit after completing j transactions. Each day: hold[j] = max(hold[j], sell[j-1] - price) and sell[j] = max(sell[j], hold[j] + price). Iterating days outer and j inner fills all states in O(nk) time and O(k) space.

A crucial optimization: one profitable transaction needs a distinct rise, and n prices contain at most n/2 disjoint rises. So when k >= n/2 the cap is not binding, and the problem collapses to the unlimited-transactions greedy (sum all positive differences), avoiding a wastefully large DP table. k = 1 and k = 2 (Stock I and III) are just special cases of this recurrence.

Step-by-Step Visualization

At most k=2 transactions

1/3

Code

Java

static int maxProfit(int k, int[] prices) {
  int n = prices.length;
  if (k >= n / 2) {
    int profit = 0;
    for (int i = 1; i < n; i++)
      profit += Math.max(0, prices[i] - prices[i-1]);
    return profit;
  }

  int[][] dp = new int[k+1][n];
  for (int t = 1; t <= k; t++) {
    int maxDiff = -prices[0];
    for (int i = 1; i < n; i++) {
      dp[t][i] = Math.max(dp[t][i-1], prices[i] + maxDiff);
      maxDiff = Math.max(maxDiff, dp[t-1][i] - prices[i]);
    }
  }
  return dp[k][n-1];
}

Tips & Gotchas

1dp[k][i] = max profit with at most k transactions up to day i

2For each day and transaction count, decide: hold or sell

3When k >= n/2, it becomes unlimited transactions (greedy)

Practice Problems

1Best Time to Buy and Sell Stock IV
2Best Time to Buy and Sell Stock III
3Best Time to Buy and Sell Stock

About the Stock / State Machine Pattern

Model the problem as states (holding stock, not holding, in cooldown) with transitions between them. Each day, you transition between states based on your action (buy, sell, hold). Track the max profit in each state.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

Climbing Stairs
Coin Change
Longest Common Subsequence
0/1 Knapsack
Edit Distance
House Robber
Longest Increasing Subsequence
Word Break

Frequently Asked Questions

Why does k >= n/2 make the limit irrelevant?

Each complete transaction needs at least one buy day and one later sell day, so n days support at most n/2 transactions. Beyond that, the constraint can never bind, and summing every positive day-over-day difference gives the optimum in O(n) with no DP table.

When is a transaction counted — at buy or at sell?

It is a convention, but it must be consistent. A common choice counts at buy: hold[j] draws from sell[j-1] - price, and sell[j] closes transaction j. Mixing conventions between the two updates is the classic source of answers that are off by one transaction.

How does Stock III (k = 2) simplify this?

With k fixed at 2, you can unroll the arrays into four variables — buy1, sell1, buy2, sell2 — updated in order each day. It is exactly the general recurrence with the j loop unrolled, running in O(n) time and O(1) space.