1178. Best Time to Buy and Sell Stock IV — At Most K

Given daily stock prices and an integer k, you may complete at most k transactions (non-overlapping). Return the maximum profit. The input is JSON {prices, k}.

Input: JSON {prices, k}.

Output: Integer — the maximum profit.

Examples

Input: {"prices":[2,4,1],"k":2}
Output: 2
Explanation: One transaction profits 2.

Input: {"prices":[3,2,6,5,0,3],"k":2}
Output: 7
Explanation: Two transactions profit 4 and 3.

Input: {"prices":[1],"k":0}
Output: 0
Explanation: No transactions allowed.

Constraints

• 0<=k<=100
• 1<=n<=1000

Asked by