#188
Best Time to Buy and Sell Stock IV
Hard State machine DP (k transactions)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Make at most k buy-sell transactions. Return the maximum profit.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: at most k trades.
Why this works: arrays buy[1..k] and sell[1..k], each built from the previous transaction's sell.
Example: k = 2, [3, 2, 6, 5, 0, 3]
buy 2 sell 6 (+4), buy 0 sell 3 (+3) → 7✦Hints open one at a time
Generalise the two-transaction version with arrays buy[1..k] and sell[1..k].
If k >= n / 2, there's effectively no limit — sum every rise.
↗Approach
For each price and each j from 1 to k: buy[j] = max(buy[j], sell[j−1] − p), sell[j] = max(sell[j], buy[j] + p).
</>Solution (Java)
import java.util.*;
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (k >= n / 2) { // effectively unlimited
int profit = 0;
for (int i = 1; i < n; i++) profit += Math.max(0, prices[i] - prices[i - 1]);
return profit;
}
int[] buy = new int[k + 1], sell = new int[k + 1];
Arrays.fill(buy, Integer.MIN_VALUE);
for (int p : prices) {
for (int j = 1; j <= k; j++) {
buy[j] = Math.max(buy[j], sell[j - 1] - p);
sell[j] = Math.max(sell[j], buy[j] + p);
}
}
return sell[k];
}
}!Common mistake
Huge k making the arrays and loops too big — handle k >= n/2 with the unlimited solution.
Complexity
- Time: O(n·k).
- Space: O(k).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon