Best Time to Buy and Sell Stock IV
HardArray
Description
You are given an integer array prices and an integer k. Find the maximum profit you can achieve by completing at most k transactions.
Examples
Input:
k = 2, prices = [2,4,1]Output:
2Explanation:
Buy at 2, sell at 4. Profit=2. No profitable second transaction possible (1 is lowest remaining).
Input:
k = 1, prices = [7,1,5,3,6,4]Output:
5Explanation:
K=1 limits to one buy-sell. Buy at 1, sell at 6 = profit 5. Best single transaction in array.
Input:
k = 3, prices = [1,2,3,4,5]Output:
4Explanation:
Strictly increasing prices: buy at 1, sell at 5 = profit 4. Extra transactions don't help when prices only rise.
Constraints
- •
1 ≤ k ≤ 100 - •
1 ≤ prices.length ≤ 1000