174. Best Time to Buy and Sell Stock IV
The array prices records a stock’s value across consecutive days — entry i is what one share trades at on day i — and the integer k caps your activity: no more than k buy–sell round trips are allowed, each round trip being a single purchase followed later by a single sale.
You may not hold more than one share at a time — you must sell the share you own before buying again — and buying and selling on the same day yields nothing. Return the maximum total profit you can achieve.
If no sequence of trades makes money, the best you can do is zero (make no trades).
Example 1:
Input: k = 2, prices = [2, 4, 1]
Output: 2
Explanation: Buy on day 0 at 2, sell on day 1 at 4 for a profit of 2. A second transaction cannot add anything.
Example 2:
Input: k = 2, prices = [3, 2, 6, 5, 0, 3]
Output: 7
Explanation: Buy at 2 sell at 6 (profit 4), then buy at 0 sell at 3 (profit 3); total 7 across the two allowed transactions.
Constraints:
- 0 ≤ k ≤ 100
- 0 ≤ prices.length ≤ 1000
- 0 ≤ prices[i] ≤ 1000
Hints:
If k is at least half the number of days, the transaction cap never binds — you can grab every upward step. Handle that as the unlimited-transactions case.
Otherwise think in states: after processing day i, what is the best profit having completed t transactions while either holding or not holding a share?
Track, for each transaction count t, the best 'currently holding' value (best profit minus the price you paid) and the best 'sold out' value. Update them day by day in O(nk).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: k = 2, prices = [2, 4, 1]
Expected output: 2