Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock IV is the boss level of the stock-trading family. You may make at most k buy-sell transactions, and you want the maximum total profit. The trick is to carry a tiny pair of running states per transaction and fold each price into them.

The slow way first

The brute-force idea explores every choice on every day: at each price, for each remaining transaction, decide buy / sell / skip. That branches exponentially. Even a careful recursion over (day, transaction, holding?) is O(n · k) states but costs memory for a full table, and a naive version re-explores overlapping subproblems again and again.

The question to ask: what is the smallest amount of state I must remember to make the next decision? It turns out I only need, for each transaction count t, two numbers: the best balance if I am currently holding a share bought as my t-th buy, and the best profit after completing t sells.

The idea: roll a buy/sell pair per transaction

Keep two arrays of length k + 1:

• buy[t] — the best balance (profit minus the price I paid) while holding the share of my t-th buy.
• sell[t] — the best profit after completing exactly t sells.

For each price, update every transaction level: I can buy my t-th share starting from the profit I had after t − 1 sells, and I can sell my held t-th share to bank profit.

The key insight: buy[t] is funded by sell[t-1], so transactions chain together — the profit from your first sale becomes the budget for your second buy.

Walk through it

Step through the animation. The price pointer scans the prices. Underneath, the buy and sell arrays update for each price. Watch sell[0] jump to 4 when the price hits 6 (buy at 2, sell at 6), and sell[1] reach 7 at the final price 3 (the second transaction: buy at 0, sell at 3). The answer is sell[k] = 7.

Pseudocode

buy[t]  = -infinity for every t in 0..k     # best balance while holding the t-th share
sell[t] = 0 for every t in 0..k             # best profit after t completed sells
for each price in prices:
    for t from 1 to k:
        buy[t]  = max(buy[t],  sell[t-1] - price)   # buy the t-th share today
        sell[t] = max(sell[t], buy[t]    + price)   # sell the held t-th share today
return sell[k]                              # best profit using up to k transactions

The Python solution

def max_profit(k, prices):
    buy = [float('-inf')] * (k + 1)
    sell = [0] * (k + 1)
    for price in prices:
        for t in range(1, k + 1):
            buy[t] = max(buy[t], sell[t - 1] - price)
            sell[t] = max(sell[t], buy[t] + price)
    return sell[k]

• buy[t] starts at -inf because you have not bought anything yet — no balance is valid.
• sell[t] starts at 0 because doing nothing earns zero profit.
• For each price, the inner loop folds it into every transaction level t from 1 to k.
• Line 6: buying your t-th share spends price out of the profit you had after t − 1 sells.
• Line 7: selling the share you are holding banks buy[t] + price. Using the freshly updated buy[t] here is fine — it models buying and selling on the same chain of days.
• sell[k] is the best profit using at most k transactions (fewer is allowed because each sell[t] keeps its old value via max).

Complexity

We only ever keep 2(k + 1) numbers, no matter how long the price history is. That rolling-state idea — carry the minimal summary per option and fold each new element in — is the heart of these DP problems.

When this pattern shows up

Practice