DP — Best Time to Buy and Sell Stock IV
↗ LeetCode: Best Time to Buy and Sell Stock IV · Hard · pattern chapter →
At most k transactions. Max profit.
Example 1 — k=2, prices=[2,4,1] → 2 (one trade: 2→4) Example 2 — k=2, prices=[3,2,6,5,0,3] → 7 (2→6 gives 4, 0→3 gives 3) Example 3 — k=0, prices=[1,3,2] → 0
Constraints — 1 ≤ k ≤ 100; 1 ≤ n ≤ 1000. Brute picks C(n, 2k) buy-sell pairs — at n=1000, k=100 that's ~10²³⁰ combinations (10¹²⁰ dead universes). 2k-state DP is O(n·k) = 10⁵ ops = <5 min even before the k≥n/2 shortcut collapses it to greedy O(n) = ~10⁶ pointer ops on a hot service.
Interview timer00:00
Approach 1 — Brute pair enumeration
Intuition. For each subset of up to k disjoint (buy, sell) pairs, sum profits. Exponential.
Complexity — Time O(C(n,2k)); Space O(k). TLE past n=20. In an interview say "state (day, transactions used, holding/not) collapses to 2k+2 variables → O(n·k) DP."
Approach 2 — 2k states DP with unlimited-k shortcut (canonical)
Insight. buy[t] = max profit after starting t-th buy; sell[t] = max profit after completing t-th sell. If k ≥ n/2, unlimited transactions → sum of positive daily diffs.
int maxProfit(int k, int[] prices) {
int n = prices.length;
if (k >= n / 2) {
int sum = 0;
for (int i = 1; i < n; i++) if (prices[i] > prices[i-1]) sum += prices[i] - prices[i-1];
return sum;
}
int[] buy = new int[k + 1], sell = new int[k + 1];
Arrays.fill(buy, Integer.MIN_VALUE);
for (int p : prices)
for (int t = 1; t <= k; t++) {
buy[t] = Math.max(buy[t], sell[t-1] - p);
sell[t] = Math.max(sell[t], buy[t] + p);
}
return sell[k];
}Complexity — Time O(n · k); Space O(k). Say aloud in an interview: "state-machine DP — same skeleton as Cooldown, With Fee, generalizes to any k."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute pair enum | O(C(n,2k)) | O(k) | TLE past n=20 |
| 2k states DP | O(n · k) | O(k) | Canonical |
When to use which
- Fixed k → 2k states.
- k unlimited → sum positive diffs.