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