Stock Trading DP: All 6 Problems Solved with One Framework

The six “Best Time to Buy and Sell Stock” problems on LeetCode are among the most frequently asked DP questions. They look different on the surface, but they all share one elegant framework. Master the framework and you can solve any variant in minutes.

The Unified Framework

Every stock problem has the same structure:

• Day i: which day are we on (0 to n-1)?
• Transactions remaining k: how many more complete buy-sell pairs can we do?
• Holding h: are we currently holding a stock (0 or 1)?

The general recurrence:

dp[i][k][0] = max(dp[i-1][k][0],           # rest
                   dp[i-1][k][1] + price[i]) # sell

dp[i][k][1] = max(dp[i-1][k][1],           # rest
                   dp[i-1][k-1][0] - price[i]) # buy (uses a transaction)

Each variant just constrains k or adds a twist to the transitions.

---

Problem I: At Most 1 Transaction

LeetCode 121. Buy once, sell once. Maximise profit.

Since k = 1, we do not need the k dimension at all. Track just “not holding” and “holding.”

def max_profit_i(prices):
    if not prices:
        return 0

    min_price = prices[0]
    max_profit = 0

    for price in prices[1:]:
        max_profit = max(max_profit, price - min_price)
        min_price = min(min_price, price)

    return max_profit

Time: O(n) | Space: O(1)

State Machine Version

def max_profit_i_sm(prices):
    # dp_hold = max profit if we are holding stock
    # dp_cash = max profit if we are not holding stock
    dp_cash = 0
    dp_hold = float('-inf')

    for price in prices:
        dp_cash = max(dp_cash, dp_hold + price)   # sell
        dp_hold = max(dp_hold, -price)             # buy (from 0, since k=1)

    return dp_cash

---

Problem II: Unlimited Transactions

LeetCode 122. No limit on transactions. Buy and sell as many times as you want.

Since k is unlimited, the k dimension collapses.

def max_profit_ii(prices):
    dp_cash = 0
    dp_hold = float('-inf')

    for price in prices:
        old_cash = dp_cash
        dp_cash = max(dp_cash, dp_hold + price)   # sell
        dp_hold = max(dp_hold, old_cash - price)   # buy (from any previous cash)

    return dp_cash

Time: O(n) | Space: O(1)

Greedy Shortcut

Since transactions are unlimited, just add every positive difference:

def max_profit_ii_greedy(prices):
    return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))

---

Problem III: At Most 2 Transactions

LeetCode 123. At most 2 complete transactions.

With k = 2, we can unroll the states:

def max_profit_iii(prices):
    # State: (cash after 0 buys, hold after 1st buy,
    #         cash after 1st sell, hold after 2nd buy)
    buy1 = float('-inf')
    sell1 = 0
    buy2 = float('-inf')
    sell2 = 0

    for price in prices:
        sell2 = max(sell2, buy2 + price)
        buy2 = max(buy2, sell1 - price)
        sell1 = max(sell1, buy1 + price)
        buy1 = max(buy1, -price)

    return sell2

Time: O(n) | Space: O(1)

Why This Order Works

We process sell2 before buy2 before sell1 before buy1. But the order does not actually matter because using today’s price for both a sell and a buy on the same day is equivalent to doing nothing (the sell and buy cancel out).

---

Problem IV: At Most k Transactions

LeetCode 188. The general case.

def max_profit_iv(k, prices):
    n = len(prices)
    if n <= 1:
        return 0

    # If k >= n/2, we can do unlimited transactions
    if k >= n // 2:
        return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))

    # dp[j][0] = max profit with j transactions, not holding
    # dp[j][1] = max profit with j transactions, holding
    dp = [[0, float('-inf')] for _ in range(k + 1)]

    for price in prices:
        for j in range(k, 0, -1):
            dp[j][0] = max(dp[j][0], dp[j][1] + price)      # sell
            dp[j][1] = max(dp[j][1], dp[j - 1][0] - price)  # buy

    return dp[k][0]

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

The k >= n/2 optimisation is critical. Without it, large k values cause TLE.

---

Problem V: With Cooldown

LeetCode 309. After selling, you must wait one day before buying again.

This adds a third state: cooldown (just sold, cannot buy).

def max_profit_cooldown(prices):
    # Three states
    dp_cash = 0           # not holding, free to buy
    dp_hold = float('-inf')  # holding stock
    dp_cool = 0           # just sold, in cooldown

    for price in prices:
        old_cash = dp_cash
        old_hold = dp_hold
        old_cool = dp_cool

        dp_cash = max(old_cash, old_cool)          # rest or exit cooldown
        dp_hold = max(old_hold, old_cash - price)  # rest or buy (from cash, not cool)
        dp_cool = old_hold + price                 # sell

    return max(dp_cash, dp_cool)

Time: O(n) | Space: O(1)

State Machine Diagram

        buy
cash ----------> hold
  ^                |
  |   rest         | sell
  |                v
  +---- cool <-----+
    (wait 1 day)

• From cash: can buy (go to hold) or rest (stay cash)
• From hold: can sell (go to cool) or rest (stay hold)
• From cool: must rest (go to cash)

---

Problem VI: With Transaction Fee

LeetCode 714. Each transaction (buy + sell) incurs a fee.

Same as Problem II but subtract fee when selling:

def max_profit_fee(prices, fee):
    dp_cash = 0
    dp_hold = float('-inf')

    for price in prices:
        old_cash = dp_cash
        dp_cash = max(dp_cash, dp_hold + price - fee)  # sell (pay fee)
        dp_hold = max(dp_hold, old_cash - price)        # buy

    return dp_cash

Time: O(n) | Space: O(1)

You can also apply the fee during buying instead of selling. The result is the same.

---

Complete Comparison

Problem	k	Constraint	States	Time	Space
I	1	None	cash, hold	O(n)	O(1)
II	Unlimited	None	cash, hold	O(n)	O(1)
III	2	None	buy1, sell1, buy2, sell2	O(n)	O(1)
IV	k	None	k * (cash, hold)	O(nk)	O(k)
V	Unlimited	1-day cooldown	cash, hold, cool	O(n)	O(1)
VI	Unlimited	Fee per txn	cash, hold	O(n)	O(1)

---

How to Identify Which Variant

Ask these questions:

1. How many transactions? 1 (Problem I), 2 (III), k (IV), unlimited (II, V, VI)
2. Any constraint after selling? Cooldown (V)
3. Any cost per transaction? Fee (VI)

---

Building Intuition: Walk Through Problem IV

Let’s trace prices = [3, 2, 6, 5, 0, 3] with k = 2:

Day	Price	buy1	sell1	buy2	sell2
0	3	-3	0	-3	0
1	2	-2	0	-2	0
2	6	-2	4	-2	4
3	5	-2	4	-1	4
4	0	0	4	4	4
5	3	0	4	4	7

Result: 7 (buy at 2, sell at 6, buy at 0, sell at 3).

---

Common Mistakes

1. Not initialising hold to negative infinity. If you start with hold = 0, you are saying you can sell stock you never bought.
2. Using the wrong old values. When updating both cash and hold in the same loop, save the old values first. Otherwise the sell might use a buy from the same day.
3. Forgetting the k >= n/2 optimisation in Problem IV, causing TLE.
4. Counting transactions wrong. A transaction is a buy-sell pair. Counting buy and sell separately leads to errors.
5. Applying fee twice. The fee is per transaction, not per buy and per sell.

---

Practice Problems

Problem	Platform	Difficulty
Best Time to Buy and Sell Stock	LeetCode 121	Easy
Best Time II	LeetCode 122	Medium
Best Time III	LeetCode 123	Hard
Best Time IV	LeetCode 188	Hard
Best Time with Cooldown	LeetCode 309	Medium
Best Time with Transaction Fee	LeetCode 714	Medium

---

Key Takeaway

All six stock problems are instances of the same state machine:

dp[day][transactions_remaining][holding_stock]

Each variant simply changes the number of allowed transactions or adds a constraint (cooldown, fee) to one of the transitions. Learn the general framework and you will never be surprised by a stock trading variant again.