Why it works
- 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.
- 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).
- 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 ↗