Skip to content
Tutorials Center
My learning

Topics

Lesson 165 of 225 ยท Dynamic Programming

Stock Buy and Sell with k Transactions

Solve the whole stock buy-and-sell family in Python: one trade, unlimited trades, at most 2 or k transactions, cooldown and fee, with one state-machine DP.

"Best time to buy and sell a stock" is one of the most famous interview questions, and it comes in a whole family of variants: one trade, as many trades as you like, at most two trades, at most k trades, a cooldown day after selling, a fee per trade. They look like six different problems. They are really one problem with different rules about what you may do on each day.

In this lesson you will learn to see the problem as a tiny state machine and write all six solutions from the same skeleton. You should already know one-dimensional DP and the rolling-array idea from memoization versus tabulation. The one-trade case also appears in array problem sets as a running-minimum exercise.

The setting

You are given prices[i], the price of one share on day i. You can hold at most one share at a time, so you must sell before buying again. Your goal is the largest possible profit. Doing nothing is allowed (profit 0).

Variant 1: one transaction

Scan the days once, remembering the cheapest price so far. On each day the best profit "if I sell today" is price - cheapest.

Variant 2: unlimited transactions

If you may trade as often as you like, you collect every upward step: profit is the sum of max(0, prices[i] - prices[i-1]). A rise from 1 to 5 over three days earns the same as three one-day rises, so you never need to hold through a dip.

Python One trade and unlimited trades

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The state machine view

Each day you are in one of two states:

  • Cash (not holding a share), with the best profit you could have.
  • Holding (one share in hand), with the best profit you could have, where the purchase price has already been subtracted.

A day can leave you in the same state (wait) or move you across: buy (cash -> holding) or sell (holding -> cash). For a limit on the number of transactions we count a transaction when you buy, or equivalently when you sell, and add a second index for how many have been used.

flowchart LR
    C["Cash<br/>(no share)"] -->|"buy: profit - price"| H["Holding<br/>(one share)"]
    H -->|"sell: profit + price"| C
    C -->|wait| C
    H -->|wait| H

Two states per transaction count; each day updates both from the day before.

Variant 3 and 4: at most 2 or k transactions

Let buy[j] be the best profit while holding a share with j transactions started, and sell[j] the best profit while in cash after completing j transactions. For each price p:

TEXT
buy[j]  = max(buy[j],  sell[j-1] - p)     # start transaction j by buying today
sell[j] = max(sell[j], buy[j] + p)        # finish transaction j by selling today

Run this for j = 1..k on every day. The answer is sell[k] (selling more times never hurts when profits are non-negative). Complexity is O(n * k) time and O(k) space.

If k >= n // 2 you can make a trade on every rising step anyway, so the problem collapses to the unlimited case. That shortcut avoids O(n * k) when k is huge.

Python At most k transactions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For [3, 3, 5, 0, 0, 3, 1, 4] one trade gives 4 (buy at 0, sell at 4), and two trades give 6: buy at 3 and sell at 5 for 2, then buy at 0 and sell at 4 for 4.

Updating buy[j] and sell[j] in this order on the same day is safe: if the best way to hold uses today's price and you also "sell" today, you would simply have bought and sold at the same price, which adds 0. The result is correct, and it lets us avoid a separate previous-day copy.

Variant 5: cooldown after selling

After you sell, you must skip the next day before buying again. Now the day-to-day moves depend on three states:

  • held: holding a share.
  • sold: just sold today (so tomorrow is frozen).
  • rest: in cash and free to buy.
TEXT
held' = max(held, rest - p)       # keep holding, or buy from rest
sold' = held + p                  # sell today
rest' = max(rest, sold)           # wait, or finish the cooldown

The answer is max(sold, rest) on the last day.

Variant 6: a fee per transaction

Pay fee once per round trip (charge it when you sell). With unlimited trades there are only two states, so it is a small change:

TEXT
cash' = max(cash, held + p - fee)
held' = max(held, cash - p)
Python Cooldown and transaction fee

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the tuple assignment, Python evaluates the whole right side before assigning, so every new value is computed from the previous day's state. That is exactly what the state machine needs. For [1, 2, 3, 0, 2] the cooldown answer is 3: buy at 1, sell at 3, skip a day, buy at 0, sell at 2.

Checking against a brute force

Because each variant is a few lines, an off-by-one is easy to miss. A top-down recursion that follows the rules literally is the best reference.

Python Random test of the state machines

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Zero problems means the three short DPs agree with the rule-following recursion on 400 random price lists.

Choosing the right variant

Rule State Time Space
One transaction cheapest so far O(n) O(1)
Unlimited sum of rises O(n) O(1)
At most k buy[j], sell[j] O(n k) O(k)
Cooldown held, sold, rest O(n) O(1)
Fee cash, held O(n) O(1)

Common mistakes

  • Starting buy at 0. Holding a share requires having bought it, so initialise "holding" to negative infinity until the first purchase.
  • Reading values updated on the same day. In the cooldown version the new sold must use the old held. Use tuple assignment or temporary variables.
  • Looping k up to a huge number. Cap it: when k >= n // 2 the answer equals the unlimited case.
  • Charging the fee twice. Charge it once per round trip, either at the buy or at the sell, never both.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. With unlimited transactions and no fee, what is the maximum profit?

    Every upward step can be captured by buying yesterday and selling today, so the best profit is the sum of the positive differences.
  2. 2. In the at-most-k DP, what do buy[j] and sell[j] hold?

    Each is the best profit in one of the two states at transaction count j, updated day by day.
  3. 3. For k >= n // 2, why can the at-most-k solution fall back to the unlimited one?

    A round trip needs two distinct days, so there can be no more than n // 2 non-overlapping trades.
  4. 4. In the cooldown version, what must the new sold value be computed from?

    You sell today the share you were holding yesterday: sold' = held + price, using the old held.
  5. 5. Why initialise the 'holding' state to negative infinity?

    Before any purchase the holding state is impossible, and negative infinity guarantees it never beats a real option.

Summary

  • Every stock problem is a small state machine: cash and holding, plus a transaction count, a cooldown state, or a fee.
  • One trade: running minimum. Unlimited: sum of positive rises.
  • At most k: buy[j] = max(buy[j], sell[j-1] - p) and sell[j] = max(sell[j], buy[j] + p); O(n k), and k >= n // 2 reduces to unlimited.
  • Cooldown adds a sold state; a fee is subtracted once per round trip.
  • Update all states from the previous day's values, and check variants against a rule-following brute force.

Next: Egg Dropping, Rod Cutting and Classic DP Puzzles, more state-design practice.