VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.4 of 16 in this moduleFree

Best Time to Buy and Sell Stock

Maximum profit from one buy and one sell: brute force over every pair, then one pass that remembers only the lowest price. Then the rules change (unlimited trades, a fee, at most k trades, a metric's largest drop) and each change adds exactly the state it needs.

about 10 min 6 Python examples 2 quick checks

Problem. prices[i] is the price on day i. Choose one day to buy and a later day to sell to maximise profit. If no profit is possible, return 0.

text
prices = [7, 1, 5, 3, 6, 4]   →   5    (buy at 1 on day 1, sell at 6 on day 4)
prices = [7, 6, 4, 3, 1]      →   0    (prices only fall)

ML context. The same scan answers "what's the biggest improvement in a validation metric after its worst point so far?" and, flipped, "what's the largest drop after a peak?", the maximum drawdown, used to watch model quality over time and to measure risk.

This problem is famous because its optimal solution is tiny, and because the follow-ups (change the trading rules) each add exactly one piece of state. That makes it the cleanest example in this module of constraints driving the design.


1. Step 1: Clarify

Question Answer Why it matters
Must I sell after buying? Yes, a later day Rules out pairing a day with itself or the past
Can I not trade at all? Yes, profit 0 Falling prices return 0, not a negative number
How many trades? One (for now) The follow-ups change this
n? Up to 10⁵ O(n²) = 10¹⁰: too slow
Empty or one day? Return 0 Edge cases

2. Step 2: Brute force

Try every buy day with every later sell day.

python
def max_profit_brute(prices):
    best = 0
    n = len(prices)
    for buy in range(n):
        for sell in range(buy + 1, n):          # sell strictly after buy
            best = max(best, prices[sell] - prices[buy])
    return best


assert max_profit_brute([7, 1, 5, 3, 6, 4]) == 5
assert max_profit_brute([7, 6, 4, 3, 1]) == 0
assert max_profit_brute([]) == 0 and max_profit_brute([5]) == 0
print("brute force works")

O(n²) time, O(1) space. At n = 10⁵: about 5 × 10⁹ pairs. Too slow, so optimise.


3. Step 3: Optimise: what does the past contribute?

Fix a sell day. Which buy day is best? The cheapest day before it, and nothing else about the past matters. So as we scan forward, keep just one number: the lowest price seen so far. Today's best profit is today's price minus that minimum.

prices [7, 1, 5, 3, 6, 4] over days with the running minimum dashed; the best trade buys at 1 on day 1 and sells at 6 on day 4 for a profit of 5.
Chart— prices [7, 1, 5, 3, 6, 4] over days with the running minimum dashed; the best trade buys at 1 on day 1 and sells at 6 on day 4 for a profit of 5.
six frames scanning the prices; the lowest price drops to 1 on day 1, the best profit becomes 4 on day 2 and 5 on day 4.
Diagram— six frames scanning the prices; the lowest price drops to 1 on day 1, the best profit becomes 4 on day 2 and 5 on day 4.
python
import random


def max_profit(prices):
    lowest = float("inf")
    best = 0
    for p in prices:
        lowest = min(lowest, p)           # the best buy day so far
        best = max(best, p - lowest)      # selling today after the best buy
    return best


def max_profit_brute(prices):
    n = len(prices)
    return max((prices[j] - prices[i] for i in range(n) for j in range(i + 1, n)), default=0)


assert max_profit([7, 1, 5, 3, 6, 4]) == 5
rng = random.Random(8)
for _ in range(500):
    prices = [rng.randint(1, 30) for _ in range(rng.randint(0, 20))]
    assert max_profit(prices) == max(0, max_profit_brute(prices))
print("one pass matches brute force: O(n) time, O(1) space")
  • Time: O(n). Space: O(1).
  • Order of the two updates: updating lowest first means p − lowest can be 0 on the day we buy, never a "sell before buy". That's why it's safe.
  • This is a dynamic program in disguise: the state "best buy so far" summarises the whole past. Module 12 makes that explicit, and the follow-ups below are exactly that.

Quick check

Why is it enough to remember only the lowest price so far?

  1. Because prices are sorted
  2. For any sell day, the best buy day before it is the cheapest one; no other information about the past can improve a sale today
  3. Because only one trade is allowed per week
  4. It isn't; you need all prices
Show the answer

B. For any sell day, the best buy day before it is the cheapest one; no other information about the past can improve a sale today — The past matters only through its minimum, so one number replaces the inner loop.


4. The ML mirror: maximum drawdown

Flip the question: the largest drop from a peak to a later low. Same scan, with a running maximum instead of a minimum.

python
def max_drawdown(values):
    peak = float("-inf")
    worst = 0.0
    for v in values:
        peak = max(peak, v)               # the highest point so far
        worst = max(worst, peak - v)      # the deepest fall from it
    return worst


accuracy = [0.81, 0.84, 0.86, 0.79, 0.83, 0.88, 0.80]
assert abs(max_drawdown(accuracy) - 0.08) < 1e-9            # 0.88 → 0.80
assert max_drawdown([1, 2, 3]) == 0
print("max drawdown works")

Monitoring a model's accuracy day by day, a drawdown alert ("accuracy fell 8 points below its best") is this exact loop.


5. When the rules change, the state changes

Each new rule asks: what do I need to remember to decide today?

one trade uses a running minimum; unlimited trades sum every rise; a fee or a cooldown needs two or three small states; at most k trades needs a table over (day, trades left); streaming prices keep the running minimum and best.
Diagram— one trade uses a running minimum; unlimited trades sum every rise; a fee or a cooldown needs two or three small states; at most k trades needs a table over (day, trades left); streaming prices keep the running minimum and best.

Rule change A: unlimited trades (one share at a time)

Brute force would try every set of non-overlapping trades: exponential.

First principles: any profitable stretch from a low to a high can be split into consecutive daily rises, and capturing every rise earns at least as much as any single longer trade. So the answer is the sum of all positive day-to-day differences.

python
import random
from functools import lru_cache


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


def brute_unlimited(prices):
    @lru_cache(maxsize=None)
    def best(day, holding):                       # exhaustive over choices, small inputs only
        if day == len(prices):
            return 0
        skip = best(day + 1, holding)
        if holding:
            return max(skip, prices[day] + best(day + 1, False))     # sell
        return max(skip, -prices[day] + best(day + 1, True))          # buy
    return best(0, False)


assert max_profit_unlimited([7, 1, 5, 3, 6, 4]) == 7       # 1→5 and 3→6
rng = random.Random(9)
for _ in range(300):
    prices = [rng.randint(1, 20) for _ in range(rng.randint(0, 12))]
    assert max_profit_unlimited(prices) == brute_unlimited(prices)
print("sum of rises matches exhaustive search")

O(n) time, O(1) space. Notice the reference solution: a small exhaustive search over "hold or not" states. That search is the general method; the greedy sum is what it simplifies to under this rule.

Rule change B: a fee per trade

Now capturing every small rise loses money to fees, so the greedy sum breaks. Keep two numbers per day: the best profit holding a share and the best profit not holding one.

python
import random


def max_profit_fee(prices, fee):
    cash, hold = 0, float("-inf")              # not holding / holding
    for p in prices:
        cash, hold = max(cash, hold + p - fee), max(hold, cash - p)
    return cash


def brute_fee(prices, fee):
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def best(day, holding):
        if day == len(prices):
            return 0
        skip = best(day + 1, holding)
        if holding:
            return max(skip, prices[day] - fee + best(day + 1, False))
        return max(skip, -prices[day] + best(day + 1, True))
    return best(0, False)


assert max_profit_fee([1, 3, 2, 8, 4, 9], 2) == 8          # buy 1, sell 8, buy 4, sell 9
rng = random.Random(10)
for _ in range(300):
    prices = [rng.randint(1, 20) for _ in range(rng.randint(0, 12))]
    fee = rng.randint(0, 5)
    assert max_profit_fee(prices, fee) == brute_fee(prices, fee)
print("two-state version matches exhaustive search")

O(n) time, O(1) space: two variables replace the whole search tree.

Rule change C: at most k trades

Now the state needs how many trades remain: for each j ≤ k, the best profit after the j-th buy and after the j-th sell. O(n · k) time, O(k) space.

python
def max_profit_k(prices, k):
    if k == 0 or len(prices) < 2:
        return 0
    if k >= len(prices) // 2:                           # enough trades to be 'unlimited'
        return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))
    buy = [float("-inf")] * (k + 1)                     # buy[j]: best profit holding after j-th buy
    sell = [0] * (k + 1)                                # sell[j]: best profit after j-th sell
    for p in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j - 1] - p)
            sell[j] = max(sell[j], buy[j] + p)
    return sell[k]


assert max_profit_k([3, 2, 6, 5, 0, 3], 2) == 7          # 2→6 and 0→3
assert max_profit_k([7, 1, 5, 3, 6, 4], 1) == 5          # same as the single-trade answer
assert max_profit_k([7, 1, 5, 3, 6, 4], 10) == 7         # same as unlimited
print("k-transaction version works")

The two consistency checks are worth saying: with k = 1 it must equal the single-trade answer, and with large k the unlimited answer. Checking special cases against simpler solutions catches bugs in the general one.

The full table

Rule State remembered Time Space
One trade lowest price so far O(n) O(1)
Unlimited trades nothing (sum rises) O(n) O(1)
Unlimited + fee holding / not holding O(n) O(1)
Unlimited + one-day cooldown holding / just sold / resting O(n) O(1)
At most k trades best after each of k buys and sells O(n · k) O(k)
Prices streaming in lowest so far, best so far O(1) per price O(1)

Quick check

Why does the 'sum every rise' answer fail once each trade costs a fee?

  1. Splitting a long rise into many small trades now pays the fee many times, so merging rises into fewer trades can earn more; the decision depends on whether you're holding, which needs state
  2. Fees make prices negative
  3. The sum is computed wrongly
  4. Fees only apply to buying
Show the answer

A. Splitting a long rise into many small trades now pays the fee many times, so merging rises into fewer trades can earn more; the decision depends on whether you're holding, which needs state — The greedy argument relied on trades being free. A fee breaks it and brings back a small state machine.


6. Saying it out loud

"Brute force tries every buy and later sell: O(n²). For any sell day, the best buy is the cheapest earlier day, so I keep a running minimum and the best profit: one pass, O(1) space. If trades were unlimited I'd sum every positive daily change; with a fee that greedy breaks, so I'd track holding versus not holding, still O(n). With at most k trades, the state grows to k buy and sell values: O(n·k)."


Check yourself

  1. Why does a running minimum replace the inner loop?
  2. Why update lowest before computing today's profit?
  3. How does maximum drawdown relate to this problem, and where is it used in ML?
  4. Why is summing every positive daily change optimal with unlimited free trades?
  5. What state does the fee version keep, and why is it needed?
  6. What two simpler answers should the k-trade version match?
Answers
  1. For each sell day, the best buy is the cheapest earlier price, so only the minimum of the past matters.
  2. It makes a same-day "buy and sell" give 0 rather than ever selling before buying.
  3. It's the mirror: largest fall after a peak, with a running maximum. Used to monitor drops in model metrics over time.
  4. Any profitable stretch decomposes into consecutive daily rises; capturing all of them earns at least as much as any set of longer trades.
  5. Best profit while holding and while not holding: whether to sell (paying the fee) depends on that.
  6. k = 1 equals the single-trade answer; k ≥ n/2 equals the unlimited answer.