At Most K Trades
prices[i] is the price of one share on day i. A trade buys one share on some day and sells it on a later day. You hold at most one share at a time, so a trade must end before the next one begins (selling and buying again on the same day is allowed).
Return the largest total profit from at most k trades. Making no trade gives 0.
Example 1
prices [5,9,2,3,8]
k 2
returns 10
Buy at 5 and sell at 9, then buy at 2 and sell at 8: 4 + 6 = 10.
Example 2
prices [5,9,2,3,8]
k 1
returns 6
With one trade only, buy at 2 and sell at 8.
Example 3
prices [9,7,4]
k 3
returns 0
The price only falls, so it is best not to trade.
Constraints
1 <= len(prices) <= 3000 <= prices[i] <= 10**41 <= k <= 50
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.