Best Time to Buy and Sell Stock IV
Max profit using at most k non-overlapping buy-sell transactions.
Open on LeetCode ↗Intuition
It's tempting to assume you must use all k transactions and design the DP around forcing exactly k trades. You may use fewer, so the real target is the best profit over AT MOST k transactions, and a correct recurrence has to let a trade be skipped for free when it wouldn't help. There's also a scaling trap: once k is at least n/2, you physically cannot fit more than n/2 profitable round trips into n days, so the limit stops binding entirely and the problem collapses to the unlimited-transactions greedy. Skipping that shortcut and building a full k-sized table for large k blows up memory for no reason.
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
Detect the unbounded case first
If k >= n // 2, no transaction cap can bind, so fall back to summing every positive daily price delta, exactly like the unlimited-transactions version. This avoids allocating O(k) state for a k that's effectively infinite.
Otherwise run a bounded state machine
Keep buy[j] and sell[j] arrays for j from 0 to k, where buy[j] is the best cash position after the j-th purchase and sell[j] is the best profit after the j-th sale. Initialize buy[j] = -infinity for all j (except handled via the loop) and sell[j] = 0. For each day's price, update buy[j] = max(buy[j], sell[j-1] - price) then sell[j] = max(sell[j], buy[j] + price) for j from 1 to k, in that order so a buy and sell can chain within one day pass.
Answer is sell[k]
sell[k] is a running max that was seeded across every smaller transaction count during the sweep, so it already represents the best result using at most k transactions, not exactly k.
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.