A day trader has a licence for a limited number of trades. A trade means one buy followed by one sell. The number k is the most trades she may make. The list prices gives the price of a share: prices[i] is the price on day i.
She can hold one share at a time. So she has to sell the share she owns before she buys another one.
Return the largest total profit she can make with at most k trades. If no trade can earn money, return 0.
Examples
Example 1:
Input: k = 2, prices = [4,1,6,3,8]
Output: 10
Explanation: Buy at 1 and sell at 6 for a profit of 5. Buy at 3 and sell at 8 for another 5. The total is 10.
Example 2:
Input: k = 1, prices = [4,1,6,3,8]
Output: 7
Explanation: With a single trade, the best is to buy at 1 and sell at 8, which gives 7.
Example 3:
Input: k = 3, prices = [5,4,3]
Output: 0
Explanation: The price keeps falling, so every trade would lose money. The best is to make none.