Best Time to Buy and Sell Stock IV

Hard#188states

You get a number k and the price of one share for each day. Make at most k trades, each a buy and a later sell, holding one share at a time. Find the largest total profit, or 0 if no trade pays. Our example: k = 2, prices [1, 6, 4, 9, 2, 5] → 11, from 1 → 9 and 2 → 5.

188 Best Time to Buy and Sell Stock IVWalkthrough · 1×

Example: k = 2, prices [1, 6, 4, 9, 2, 5]: three rises, room for two trades. Watch days 4 and 5: the 2nd share switches to the one bought at 2 after 1 → 9, and that plan overtakes 1 → 6 and 4 → 9.

daystartprice011624394255sell[0]0buy[1]sell[1]0buy[2]sell[2]0
today, this stepbest money in this state after that daycomes from hereanswer and its trades

sell[j]: the most money with j trades finished. Before day 0 nothing is sold: sell = [0, 0, 0]

01/45
restart · back · play · step
Speed
1function maxProfit(k, prices):
2 sell = array of k + 1 zeros // j trades done
3 buy = array of k + 1, buy[1..k] = -prices[0]
4 for each p in prices:
5 for j from 1 to k:
6 buy[j] = max(buy[j], sell[j - 1] - p)
7 sell[j] = max(sell[j], buy[j] + p)
8 return sell[k]
state
buy
–
sell
[0, 0, 0]
p
–
j
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. buy[j] and sell[j] are the states of the j-th trade: holding its share, and done with it. The j-th buy starts from sell[j − 1], the money after j − 1 trades, so trades follow one another and none overlap.
  2. k caps the count because there is no sell[k + 1]. With three rises and k = 2 the table has to choose: riding through the dip 6 → 4 costs 2, dropping the smallest rise 2 → 5 would cost 3, so 1 → 9 and 2 → 5 (11) beat 1 → 6 and 4 → 9 (10).
  3. Each day a state keeps yesterday’s value or moves in from the state before it at today’s price, so sell[k] is the best over every way to place at most k trades.

Complexity

Time O(n·k): on each of n days the inner loop updates two numbers for each of k trades. Memory O(k): the two arrays, overwritten in place day after day.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.