Best Time to Buy and Sell Stock IV
You are given an integer array prices where prices[i] is the price of a given stock on the i^th day, and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions: i.e., you may buy at most k times and sell at most k times.
Note: You may not engage in multiple transactions simultaneously, i.e., you must sell the stock before you buy again.
Example 1
Input
k = 2, prices = [2,4,1]Output
2Buy on day 1 at price 2 and sell on day 2 at price 4, for a profit of 2.
Example 2
Input
k = 2, prices = [3,2,6,5,0,3]Output
7Buy on day 2 at price 2 and sell on day 3 at price 6 for profit 4, then buy on day 5 at price 0 and sell on day 6 at price 3 for profit 3.
Constraints
- 1 <= k <= 100
- 1 <= prices.length <= 1000
- 0 <= prices[i] <= 1000