Best Time to Buy and Sell Stock IV
Problem Statement
You are given an integer k and an array prices, where prices[i] is the price of a stock on day i. You may complete at most k transactions. One transaction is one buy followed by one sell, and you may not hold more than one share at a time. Return the maximum profit you can achieve.
Input
An integer k and an integer array prices representing daily stock prices.
Output
An integer: the maximum profit achievable with at most k completed transactions.
Constraints
- •
0 <= k <= 100 - •
0 <= prices.length <= 1000 - •
0 <= prices[i] <= 1000
Examples
Example 1
k = 2, prices = [2,4,1]
2Example 2
k = 2, prices = [3,2,6,5,0,3]
7Example 3
k = 4, prices = [1,2,3,4,5]
4Learning Objectives
- Model stock trading as a state machine with holding and not-holding states.
- Track transaction count by completed sells while updating buy and sell arrays.
- Recognise the unlimited-transactions shortcut when **k >= n / 2**.
- Compress the day dimension so the solution uses O(k) memory.
Intuition
A transaction has two phases: buy, then sell. The hard part is remembering both how many transactions remain and whether you are currently holding a share. That is exactly a state machine.
For each transaction number t, keep two best profits after processing the current day. buy[t] means the best profit while holding one share after starting the t-th transaction. sell[t] means the best profit while holding no share after completing at most t transactions.
On each price, you either keep your previous state or take the transition edge. To enter buy[t], you must come from sell[t - 1] and pay today's price. To enter sell[t], you must come from buy[t] and receive today's price. This gives a compact O(n * k) state-machine DP.
If k >= n / 2, the transaction limit cannot bind, because each transaction needs at least a buy day and a later sell day. Then the answer is simply the sum of all positive adjacent price increases.
Common mistakes
- ×Treating **k** as the number of buys instead of the number of completed buy-sell transactions.
- ×Forgetting the holding state and trying to choose transactions as independent intervals greedily.
- ×Missing the unlimited-transactions shortcut, which can waste work when **k** is large.
- ×Initialising buy states to 0, which pretends you can hold a stock without paying for it.
- ×Returning a holding state instead of **sell[k]**; final profit should not include an unsold stock.
State Definition
After processing days up to the current day, let buy[t] be the maximum profit while holding one share after buying for the t-th transaction. Let sell[t] be the maximum profit while holding no share after completing at most t transactions. The answer after all days is sell[k].
State Transition
For each day price p and each transaction count t from 1 to k:
buy[t] = max(buy[t], sell[t - 1] - p)
This either keeps holding from before or buys today using profit from one fewer completed transaction.
sell[t] = max(sell[t], buy[t] + p)
This either keeps not holding from before or sells today to complete the t-th transaction.
Base cases: sell[0] = 0 because zero transactions with no stock earns zero profit. Each buy[t] starts as -prices[0], representing buying on day 0. If there are no prices or k = 0, return 0.
Solutions
Solution: O(k) state-machine DP
Use this for the general at-most-k stock problem. It handles small and moderate k, while the early unlimited-transactions branch handles very large k efficiently.
Maintain two arrays for the current best holding and not-holding profits for every transaction count. Each price relaxes the buy edge and sell edge of the state machine. Because the current day only depends on previous best values, the day dimension is compressed away.
Step-by-step
- Return 0 when there are no prices or no allowed transactions.
- If k >= n / 2, sum every positive adjacent increase because the limit cannot restrict trading.
- Initialise every buy[t] to -prices[0] and every sell[t] to 0.
- For each later day, update buy[t] from sell[t - 1] - price, then update sell[t] from buy[t] + price.
- Return sell[k], the best profit while not holding after at most k transactions.
O(n * k)
O(k)
The unlimited branch runs in O(n) time and O(1) space when k is large.
Java implementation
Dry Run
Sample input
k = 2, prices = [3,2,6,5,0,3]. Track the best holding and not-holding profits after each day.
| day | price | buy[1] | sell[1] | buy[2] | sell[2] |
|---|---|---|---|---|---|
| 0 | 3 | -3 | 0 | -3 | 0 |
| 1 | 2 | -2 | 0 | -2 | 0 |
| 2 | 6 | -2 | 4 | -2 | 4 |
| 3 | 5 | -2 | 4 | -1 | 4 |
| 4 | 0 | 0 | 4 | 4 | 4 |
| 5 | 3 | 0 | 4 | 4 | 7 |
After the last day, sell[2] = 7, representing profit 4 from buying at 2 and selling at 6, plus profit 3 from buying at 0 and selling at 3.
Complexity Analysis
The state-machine DP is O(n * k) time and O(k) space. The large-k branch prevents the algorithm from doing unnecessary transaction-state work when the problem has effectively unlimited trades.
O(k) state-machine DP
O(n * k)
O(k)
The unlimited branch runs in O(n) time and O(1) space when k is large.
Interview Tips
Describe the DP as a state machine, not as a collection of ad hoc formulas. Name the two states, explain the transition into each state, and clarify that a transaction is counted when a sell completes. Then mention the k >= n / 2 shortcut before coding.
Likely follow-ups
- How would you modify the state machine for a one-day cooldown after selling?
- How would a fixed transaction fee change the sell transition?
- Can you solve the special case of at most two transactions with constant space variables?
- How would you return the actual buy and sell days for an optimal strategy?
Similar Problems
Key Takeaways
- Stock DP becomes manageable when modelled as holding versus not-holding states.
- The transaction count advances on sell, because a full buy-sell pair has completed.
- When **k >= n / 2**, the at-most-k limit is equivalent to unlimited transactions.
- The day dimension can be compressed because each state only needs previous best profits.