LeetCode #188 Hard

Best Time to Buy and Sell Stock IV

Max profit using at most k non-overlapping buy-sell transactions.

dynamic-programmingarraystate-machine

02

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.

03

Approach

1

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.

2

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.

3

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.

04

Solution & live demo

python

▶1class Solution:
▶2    def maxProfit(self, k: int, prices: list[int]) -> int:
▶3        n = len(prices)
▶4        if n < 2 or k == 0:
▶5            return 0
▶6        if k >= n // 2:
▶7            total = 0
▶8            for i in range(1, n):
▶9                total += max(prices[i] - prices[i - 1], 0)
▶10            return total
▶11        buy = [float('-inf')] * (k + 1)
▶12        sell = [0] * (k + 1)
▶13        for i in range(n):
▶14            price = prices[i]
▶15            for j in range(1, k + 1):
▶16                buy[j] = max(buy[j], sell[j - 1] - price)
▶17                sell[j] = max(sell[j], buy[j] + price)
▶18        return sell[k]

05

Edge cases

k = 0

No transactions allowed at all; sell stays all zeros (or the loop over j never runs), so the answer is 0.

k >= n/2

Routed to the unlimited-transactions greedy shortcut, avoiding an unnecessarily large k-sized DP table.

Fewer than 2 price points

No valid transaction exists regardless of k; the day loop does not run and the answer stays 0.

All prices identical

Every buy/sell pair yields zero gain, so sell[j] never rises above 0 for any j, correctly reporting 0 profit.

06

Complexity

Time

O(n*k), O(n) when k is large enough to trigger the shortcut

Space

O(k)

Falls back to O(1) extra space in the unlimited-transaction shortcut path.