Best Profit With K Trades

prices[i] is the price of one share on day i. A trade means buying one share on some day and selling it on a later day. You may make at most k trades, and you can hold only one share at a time, so a share must be sold before the next one is bought (selling and buying again on the same day is allowed).

Write max_profit(prices, k) that returns the largest total profit you can make. Making no trades at all gives a profit of 0, so the answer is never negative.

Examples

max_profit([3, 8, 2, 9, 4, 6], 2)   # returns 12
max_profit([3, 8, 2, 9, 4, 6], 1)   # returns 7
max_profit([1, 5, 2, 8, 3, 10], 2)  # returns 14
max_profit([9, 7, 5, 3], 3)         # returns 0

In the third example the three rises are worth 4, 6 and 7, but with two trades it is better to buy at 1, sell at 8, then buy at 3 and sell at 10.

Constraints

• 0 <= len(prices) <= 600
• 0 <= prices[i] <= 10000
• 0 <= k <= 100