Best Time to Buy and Sell Stock IV
Find the maximum profit from at most k buy-and-sell transactions, keeping the best profit after each j-th buy and j-th sell and updating all of them every day.
Problem Understanding
Best Time to Buy and Sell Stock IV (LeetCode 188): given daily prices and an integer k, return the maximum profit from at most k transactions. You can hold at most one share at a time, so you must sell before you buy again.
Examples: k = 2, prices = [2,4,1] → 2; k = 2, prices = [3,2,6,5,0,3] → 7.
The Intuition: One Running Best per Stage
Line the possible situations up in order: holding the 1st share, after the 1st sale, holding the 2nd share, and so on up to the k-th sale. Each day, every situation either stays as it was or is reached from the one before it:
- buy[j] comes from sell[j − 1] by paying today's price.
- sell[j] comes from buy[j] by receiving today's price.
- Keep the best of staying and moving, and the last stage, sell[k], is the answer.
With k = 1 this is Best Time to Buy and Sell Stock; with unlimited k it is Stock II. The same buy/sell state machine, with a different rule, is Stock with Cooldown.
Interactive Walkthrough
AT MOST 2 TRADES
BEFORE DAY 0
day
0
1
2
3
4
5
price
buy 1
sell 1
buy 2
sell 2
day
:
k
2
profit
:
At most 2 trades. Before day 0 no share can be held (buy = −∞) and every sell is 0
Next
Day 0, price 3: buy 1 = 0 − 3 = −3; buy 2 = 0 − 3 = −3
prices
k
Each column is a day and each row a state; solid cells are the states that improved that day. Try Three swings and change k from 3 to 2 to see the answer drop.
Dry Run Table
Input: k = 2, prices = [3,2,6,5,0,3].
| Day | Price | What improves |
|---|---|---|
| 0 | 3 | buy 1 = −3, buy 2 = −3 |
| 1 | 2 | buy 1 = −2, buy 2 = −2 |
| 2 | 6 | sell 1 = −2 + 6 = 4, sell 2 = 4 |
| 3 | 5 | buy 2 = 4 − 5 = −1 |
| 4 | 0 | buy 1 = 0, buy 2 = 4 − 0 = 4 |
| 5 | 3 | sell 2 = 4 + 3 = 7 |
Answer: sell 2 = 7 (buy at 2, sell at 6; buy at 0, sell at 3).
The Solution Template
Two arrays of k + 1 states, updated every day.
Best Time to Buy and Sell Stock IV Code
1var maxProfit = function(k, prices) {2 const buy = new Array(k + 1).fill(-Infinity);3 const sell = new Array(k + 1).fill(0);4 for (const price of prices) {5 for (let j = 1; j <= k; j++) {6 buy[j] = Math.max(buy[j], sell[j - 1] - price);7 sell[j] = Math.max(sell[j], buy[j] + price);8 }9 }10 return sell[k];11};
Edge Cases & Common Mistakes
- Falling prices: every state stays at its start and the answer is 0.
- One day: no trade possible, answer 0.
- Huge k: cap it, or switch to the Stock II sum of rises when k ≥ n / 2.
- Initialising buy to 0: pretends you already hold a free share; use −∞ (or a very negative number).
- Counting a transaction at the buy or at the sell: either works if you are consistent; here a transaction is counted when it is bought.
Summary
Keep buy[j] and sell[j] for j = 1..k; each day buy[j] = max(buy[j], sell[j − 1] − price) and sell[j] = max(sell[j], buy[j] + price). Return sell[k]. O(n · k) time, O(k) space.
More practice: DSA interview questions with answers · patterns cheat sheet