Best Time to Buy and Sell Stock IV

Hard

You are given an integer array nums where nums[i] is the price of a stock on day i, and an integer k. Return the maximum profit achievable with at most k transactions. You may not hold more than one share at a time.

Example 1

Input:  nums = [2,4,1], k = 2
Output: 2

Example 2

Input:  nums = [3,2,6,5,0,3], k = 2
Output: 7

Constraints

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