Problem Statement

Best Time to Buy and Sell Stock IV

You have a list called prices, where prices[i] is the cost of one share of a stock on day i. You also get a number k. You want to make the most money you can by buying low and selling high, but you can do this trade at most k times. One trade means one buy and one later sell. You can only own one share at a time, so you must sell before you buy again. The goal is the biggest total profit. Here is a useful shortcut: each full trade needs at least two days (one to buy, one to sell), so the most trades that could ever help is n/2, where n is the number of days. If k is already that big or bigger, the limit on trades does not matter at all, and we can just grab every upward move. When k is smaller, we have to be careful about which k trades to pick, and for that we use dynamic programming.

hardDynamic ProgrammingDynamic ProgrammingTime: O(n * k) · Space: O(n * k)

Signals to notice

at most k transactionsgeneralized buy/sellstate machine with transaction count

Brute force first

Try all possible k-transaction combinations. Each transaction pair is chosen independently. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

3D DP: dp[t][i] = max profit using at most t transactions up to day i. dp[t][i] = max(dp[t][i-1], max over j<i of (prices[i] - prices[j] + dp[t-1][j-1])). Optimize inner max to with running maximum. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `k=2, prices=[3,2,6,5,0,3]`

init: buy=[-inf,-inf,-inf], sell=[0,0,0]
price=3: buy=[_,-3,-3], sell=[0,0,0] (nothing profitable yet)
price=2: buy=[_,-2,-2], sell=[0,0,0] (cheaper entry lowers cost)
price=6: sell[1]=max(0,-2+6)=4, sell[2]=4 -> sell=[0,4,4]
price=5: buy[2]=max(-2,4-5)=-1; sell stays [0,4,4]
price=0: buy[1]=0, buy[2]=max(-1,4-0)=4 (re-buy after 1st txn)
price=3: sell[2]=max(4,buy[2]+3)=max(4,7)=7 -> sell=[0,4,7]
return max(sell)=7

What must stay true

At each day, you either do nothing or complete a transaction's sell. The running maximum trick avoids re-scanning: maxDiff = max(maxDiff, dp[t-1][j-1] - prices[j]), then dp[t][i] = max(dp[t][i-1], prices[i] + maxDiff). When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

buy[0..k] = -inf;  sell[0..k] = 0
for price in prices:
    for t = 1..k:
        buy[t]  = max(buy[t],  sell[t-1] - price)   # best to be holding in t-th txn
        sell[t] = max(sell[t], buy[t]  + price)      # best after closing t-th txn
return max(sell)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not handling the case where k ≥ n/2 — with enough transactions, you can capture every profit, reducing to the unlimited transactions problem (much simpler greedy). When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Dynamic Programming Pattern