119. Best Time to Buy and Sell Stock IV

Given an integer k and an integer array prices, find the maximum profit you can achieve with at most k transactions. You may not hold multiple stocks simultaneously.

Input: Integer k and integer array prices.

Output: Integer — maximum profit with at most k transactions.

Examples

Input: 2,[3,2,6,5,0,3]
Output: 7
Explanation: Buy at 2, sell at 6 (profit 4). Buy at 0, sell at 3 (profit 3). Total 7.

Input: 2,[1,2,3,4,5]
Output: 4
Explanation: Buy at 1, sell at 5. One transaction suffices.

Input: 2,[7,6,4,3,1]
Output: 0
Explanation: No profitable transaction.

Constraints

• 0<=k<=100
• 0<=prices.length<=1000
• 0<=prices[i]<=1000

Asked by