Best time to buy and sell stock IV
MediumThe four-state machine, generalised to k
Problem
Maximize profit with at most k transactions.
Track best buy/sell profit for each of the k allowed transactions as you scan prices.
The idea
Keep a buy and a sell value for each of the k transactions and update them all each day. When k is at least n/2 the constraint is irrelevant and the unlimited-transaction greedy applies.
The trick
- O(n·k), or O(n) when k >= n/2 via the greedy shortcut.
- Two arrays of length k, updated in transaction order.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — k=2, [2,4,1] Values: 2, 4, 1.
1dp over k transactions: for each price update buy[j],sell[j]Input
- array
- [2, 4, 1]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- k = 2, prices = [2, 4, 1]
- Output:
- 2
- Explanation:
- One trade (buy 2, sell 4) → 2.
Example 2
- Input:
- k = 2, prices = [3, 2, 6, 5, 0, 3]
- Output:
- 7
- Explanation:
- Two trades earn 7.
Example 3
- Input:
- k = 1, prices = [1, 5, 3]
- Output:
- 4
- Explanation:
- Best single trade → 4.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.