Best Time to Buy and Sell Stock IV
Best Time to Buy and Sell Stock IV: max profit using at most k non-overlapping buy-sell transactions.
- 1 <= k <= 100
- 1 <= prices.length <= 1000
- 0 <= prices[i] <= 1000
Intuition
Best time to buy and sell stock iv generalises the whole family: at most k transactions, for any given k. Problem 121 is k = 1 and problem 123 is k = 2, so their hand-written state variables become a loop over a table here.
The state is the same idea, indexed rather than named:
- buy[j] is the best balance after opening the j-th transaction; sell[j] is the best balance after closing it.
Each day, every j from 1 to k updates: buy[j] = max(buy[j], sell[j-1] − price) funds the j-th purchase from the profit of the previous j−1 completed transactions, and sell[j] = max(sell[j], buy[j] + price) closes it. That dependency on sell[j-1] is what keeps the transactions ordered and non-overlapping.
The optimisation that matters is the large-k case. A transaction needs at least two days, so more than n/2 transactions can never all be used:
When k >= n/2, the cap stops binding and the problem becomes the unlimited version — solvable by summing every positive consecutive difference in O(n). Skipping this check is the usual cause of a time limit exceeded, because k can be given as a value far larger than the array.
Initialise every buy[j] to negative infinity so an unopened transaction never appears profitable, and every sell[j] to 0, since making no transaction is always allowed.
The answer is sell[k], which already accounts for using fewer than k transactions when that is better.
The general case: k chained buy/sell pairs instead of two. The crucial optimisation is noticing that when k >= n/2 the limit stops binding — there aren't enough days to use that many transactions — so it degenerates to the unlimited version.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n*k), O(n) when k is large enough to trigger the shortcut time and O(k) space.
Generalise the earlier variants
Problems 121 and 123 are k = 1 and k = 2. Their named state variables become an indexed table here, with the same transitions in a loop.
Short-circuit when k is large
A transaction needs two days, so more than n/2 transactions can never be used. When k >= n/2 the cap stops binding — sum all positive differences in O(n). Skipping this causes a time limit exceeded.
Define the indexed states
buy[j] is the best balance after opening the j-th transaction and sell[j] after closing it. Both are arrays of size k + 1, indexed by transaction number.
Initialise correctly
Set every buy[j] to negative infinity and every sell[j] to 0. A buy state starting at 0 looks profitable when unopened and corrupts every later transaction.
Update buy from the previous sell
buy[j] = max(buy[j], sell[j-1] - price) funds the j-th purchase from the previous transactions' profit. This dependency keeps the transactions ordered and non-overlapping.
Update sell from the current buy
sell[j] = max(sell[j], buy[j] + price) closes the j-th transaction. Since fewer transactions are always permitted, this never drops below sell[j-1].
Return the final sell state
The answer is sell[k], which already covers using fewer than k transactions — each state carries the best achievable value rather than requiring exactly that many trades.
Cost of the tabulation
Each day updates k transaction states, giving O(n · k) time and O(k) space — reduced to O(n) by the large-k short-circuit.
Solution & live demo
Common pitfalls
Allocating a k-sized table without the shortcut
buy = [float('-inf')] * (k + 1) # with k up to 10^9if k >= n // 2:
# unlimited transactionsk can far exceed the number of possible transactions, so the array blows memory for no benefit. Beyond n/2 pairs the constraint is vacuous and the greedy sum of positive deltas is exact.
Iterating j downward
for j in range(k, 0, -1):
for j in range(1, k + 1):
buy[j] depends on sell[j-1] from the same day, so the lower index must be updated first. Descending order feeds it yesterday's value and undercounts the chained profit.
Seeding buy to zero
buy = [0] * (k + 1)
buy = [float('-inf')] * (k + 1)A zero seed means "holding a share that cost nothing", which lets every transaction level claim free profit. Negative infinity forces each level to be reached through a genuine purchase.
Edge cases
No transactions allowed at all; sell stays all zeros (or the loop over j never runs), so the answer is 0.
Routed to the unlimited-transactions greedy shortcut, avoiding an unnecessarily large k-sized DP table.
No valid transaction exists regardless of k; the day loop does not run and the answer stays 0.
Every buy/sell pair yields zero gain, so sell[j] never rises above 0 for any j, correctly reporting 0 profit.