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 on day 1, sell on day 2. Profit = 2.
Input:
k = 1, prices = [7,1,5,3,6,4]Output:
5Explanation:
With only 1 transaction allowed, buying on day 2 (price=1) and selling on day 5 (price=6) yields a profit of 5. This is the maximum profit possible with a single buy-sell transaction.
Input:
k = 3, prices = [1,2,3,4,5]Output:
4Explanation:
Even though up to 3 transactions are allowed, the prices are strictly increasing. The optimal strategy is buying on day 1 (price=1) and selling on day 5 (price=5) for a profit of 4. Multiple transactions would not improve the result.
Constraints
- •
1 ≤ k ≤ 100 - •
1 ≤ prices.length ≤ 1000