188. Best Time to Buy and Sell Stock IV

188

HardStock and State-Machine DPBounded-transaction DP with big-k greedy shortcutk-transaction state machine

Best Time to Buy and Sell Stock IV

Given an integer k and an array prices where prices[i] is the price of a stock on day i, find the maximum profit achievable with at most k transactions. You may not hold more than one share at a time and must sell before buying again.

Open official problem prompt ↗

In plain English

Maximize profit with a configurable ceiling of k round-trip trades.

Picture it like this

Like having exactly k reusable train tickets: each ticket is one buy-and-sell journey, and the profit from spending one ticket funds the next, but you can never use more than k in total.

Example

Input: k = 2, prices = [3, 2, 6, 5, 0, 3]
Output: 7
Why: Buy at 2 sell at 6 (+4), then buy at 0 sell at 3 (+3); total 7 with two transactions.

Constraints

1 <= k <= 1001 <= prices.length <= 10000 <= prices[i] <= 1000

Pattern lesson

See the pattern, then code

k-transaction state machine

↗

Stock and State-Machine DP

A small set of modes such as holding, free, cooldown, or transactions left.. Maintain k buy states and k sell states. When k is at least half the number of days, the cap is not binding and the problem collapses to the unlimited greedy of problem 122.

New words, made simpleKnow these before the algorithm

buy[j]: Best profit while holding a share during the j-th transaction.
sell[j]: Best profit after completing the j-th sale.
Binding cap: When k is small enough that it actually limits trades; if k is large the cap does not matter.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

2D table dp[t][day]

Correct but memory-heavy and easy to mis-index.

Fill a (k+1) x n table of best profit using at most t transactions through each day.

Time O(n * k)Space O(n * k)

Best choiceRolling buy/sell arrays + big-k shortcut

Constant-per-transaction memory and avoids blowups when k is huge relative to n.

Keep length-(k+1) buy and sell arrays and relax them per price; short-circuit to unlimited greedy when k >= n/2.

Time O(n * k)Space O(k)

The rule we keep true

Invariant

After processing a price, sell[j] equals the best profit using at most j transactions over the prices seen so far.

Why this is correct

Reasoning

buy[j] can only draw capital from sell[j-1] (the profit of one fewer transaction), so transactions are chained and non-overlapping; the k >= n/2 shortcut is valid because with n days you can never complete more than n/2 disjoint transactions, so a larger k is equivalent to unlimited.

The algorithm in three movesSay these aloud before coding

1Handle empty prices or k = 0 by returning 0

k=2 < n//2=3, use DP

2If k >= n // 2, sum every positive consecutive difference (unlimited case)

buy[1]=-2,sell[1]=4 after day 3

3Otherwise keep buy[1..k] = -inf and sell[0..k] = 0

sell[2]=7 after day 6

4For each price, for j from 1 to k relax buy[j] = max(buy[j], sell[j-1] - price) then sell[j] = max(sell[j], buy[j] + price)

5Return sell[k]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readprice 2

2 · AskCheapest entry for trade 1?

3 · Update statebuy[1]=-2

4 · Resultbuy[1] rises to -2.

Key takeaway

Two transactions: buy at 2 sell at 6, buy at 0 sell at 3.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Trivial guards
No days or zero transactions means zero profit.
2
Lines 6-7Big-k shortcut
When k is at least n/2 the cap is irrelevant, so use the O(n) unlimited greedy.
3
Lines 8-9State arrays
buy[j] impossible until entered (-inf); sell[j] starts at 0 (do nothing).
4
Lines 10-13Relax per price
For each transaction slot, first update holding, then update the closed profit, chaining off sell[j-1].
5
Lines 14Answer
sell[k] is the best using up to k transactions.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

k = 0 or empty prices returns 0
k larger than n/2 routes through the unlimited greedy branch
All-decreasing prices give 0

Common beginner mistakes

Allocating an O(n*k) table when k can be 100 and mis-estimating memory (the shortcut plus 1D arrays avoids this)
Iterating j in the wrong direction or updating sell[j] before buy[j]
Forgetting the k >= n/2 fast path and timing out or overflowing on adversarial inputs
Off-by-one from using k instead of k+1 sized arrays

Check your understanding

Why can we safely treat any k >= n/2 as unlimited transactions?

PyPython 3 · solution.py

Optimal

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

Time complexityO(n * k)Optimized

Space complexityO(k)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleBloombergCitadel

Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock IV

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Stock and State-Machine DP