#188 Best Time to Buy and Sell Stock IV
the problem
In plain words
prices[i] is a stock's price on day i, and k is the most trades you may complete (a trade is a buy followed by a later sell). You can never hold more than one share. Return the largest total profit.
in k = 2, prices = [2,4,1]
out 2
Buy at 2, sell at 4.
in k = 2, prices = [3,2,6,5,0,3]
out 7
Buy at 2, sell at 6 (+4); buy at 0, sell at 3 (+3).
- 1 ≤ k ≤ 100
- 1 ≤ prices.length ≤ 1000
- 0 ≤ prices[i] ≤ 1000
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternState-machine DP
Put the trade count into the state: buy[t] = best profit while holding the t-th share, sell[t] = best profit after t sales. Every day, walk t = 1..k: buy[t] grows from sell[t − 1], and sell[t] grows from buy[t].
solutions
From brute force to optimal
best(day, buysLeft, holding): rest, buy if a buy is left, or sell.
- Past the last day → 0.
- Return the best of resting and the one legal action.
Act or wait every day, nothing cached.
Recursion depth n.
class Solution { public int maxProfit(int k, int[] prices) { return best(prices, 0, k, false); } /** Best profit from day i on, with `buysLeft` purchases still allowed. */ private int best(int[] prices, int i, int buysLeft, boolean holding) { if (i == prices.length) return 0; int rest = best(prices, i + 1, buysLeft, holding); // do nothing today int act = 0; if (holding) act = prices[i] + best(prices, i + 1, buysLeft, false); // sell else if (buysLeft > 0) act = -prices[i] + best(prices, i + 1, buysLeft - 1, true); // buy return Math.max(rest, act); }}n × (k + 1) × 2 states; cache each.
- int[n][k + 1][2] memo, −1 = unknown.
- Check, compute, store.
2n(k + 1) states, O(1) each.
The 3D memo.
class Solution { public int maxProfit(int k, int[] prices) { int[][][] memo = new int[prices.length][k + 1][2]; // -1 = unknown (answers are never negative) for (int[][] day : memo) for (int[] row : day) Arrays.fill(row, -1); return best(prices, 0, k, 0, memo); } private int best(int[] prices, int i, int buysLeft, int holding, int[][][] memo) { if (i == prices.length) return 0; if (memo[i][buysLeft][holding] != -1) return memo[i][buysLeft][holding]; int rest = best(prices, i + 1, buysLeft, holding, memo); int act = 0; if (holding == 1) act = prices[i] + best(prices, i + 1, buysLeft, 0, memo); else if (buysLeft > 0) act = -prices[i] + best(prices, i + 1, buysLeft - 1, 1, memo); return memo[i][buysLeft][holding] = Math.max(rest, act); }}2k states, updated in chain order every day.
- buy[1..k] = −∞, sell[0..k] = 0.
- For each price p, for t = 1..k: buy[t] = max(buy[t], sell[t − 1] − p); sell[t] = max(sell[t], buy[t] + p).
- Return sell[k].
n days × k trades × 2 updates (10⁵ at LeetCode's limits).
Two arrays of k + 1 ints.
class Solution { public int maxProfit(int k, int[] prices) { int[] buy = new int[k + 1]; // buy[t]: best profit while holding the t-th share int[] sell = new int[k + 1]; // sell[t]: best profit after t completed sales (sell[0] = 0) Arrays.fill(buy, Integer.MIN_VALUE / 2); // nothing bought yet for (int p : prices) { for (int t = 1; t <= k; t++) { buy[t] = Math.max(buy[t], sell[t - 1] - p); // keep holding, or buy after t - 1 sales sell[t] = Math.max(sell[t], buy[t] + p); // keep, or sell the t-th share today } } return sell[k]; // "at most k": sell[k] is never below sell[t] for t < k }}The chain of 2k states
in the room
How to say it in the interview
talk track
- Generalise Stock III out loud: "two trades was four states; k trades is 2k states in a chain."
- Mention the shortcut: if k ≥ n/2 the limit can't bind (there are at most n/2 non-overlapping trades), so add every positive rise in O(n).
- Complexity: O(n·k) time, O(k) memory.
traps
- Starting buy[t] at 0 — that is a free share. Use −∞ (
Integer.MIN_VALUE / 2). - Allocating an n × k table when k is huge: check the k ≥ n/2 shortcut first.
what they ask next
Follow-ups
What if k can be 10⁹?
If k ≥ n/2, add every positive day-to-day rise (O(n)). Otherwise k < n/2, so the O(n·k) DP stays small.
Add a cooldown or a fee?
Put them on the arrows, exactly as in LC 309 and LC 714.
before you submit
Edge cases to test
- k = 1 → the same as Stock I.
- k at least half the number of days → the sum of every rise.
- One day → 0.
practise next
Similar problems
- #123Best Time to Buy and Sell Stock IIIHardin DP Patterns
- #309Best Time to Buy and Sell Stock with CooldownMediumin DP Patterns
- #122Best Time to Buy and Sell Stock IIMediumin Arrays & Strings