Carry the Best So Far: One Buy, One Later Sell
A reseller tracks the daily price of a second-hand game console: 9, 4, 7, 3, 8 and 6 (in hundreds). They may buy once and sell once, on a later day. What is the biggest profit they could have made? Checking every buy day against every later sell day works, but one walk through the prices is enough.
The rule
Walk once, remembering the cheapest day behind you.
For any sell day, the best buy day is simply the cheapest day before it. So you never need to look back: carry that cheapest price along with you, and at each day ask "what if I sold today?"
def best_gain(prices):
cheapest = float("inf") # no day seen yet
best = 0 # not trading at all earns 0
for price in prices:
cheapest = min(cheapest, price)
best = max(best, price - cheapest)
return bestOne pass, n steps, two variables. Starting best at 0 covers the falling market: if prices only go down, the right move is not to trade.
This is the simplest sliding window you will meet. Picture a window whose left edge sits on the cheapest day so far and whose right edge is today. The right edge moves every day; the left edge jumps forward only when a new cheapest day arrives, because from then on every sale is better off buying there. The next lessons give that left edge more interesting reasons to move.
Notice what the code never stores: which day was cheapest. It keeps only the price. If the question also asked for the buy and sell days, you would carry the day number alongside the price and record both whenever best improves.
The shortcut
Carry two numbers, "best start so far" and "best answer so far", and update both at each step. Many one-pass problems collapse to this: the best start can be the cheapest price, the smallest running total, or the earliest valid position.
Days 1 and 2: 9, then 4
Cheapest becomes 9, then 4. Selling on either day gains nothing yet: best is 0.
The trap is the tempting shortcut "largest price minus smallest price". The largest price might come before the smallest, and selling before you buy is not allowed.
Drills
Answer fast — trust the rule.
What does best_gain([8, 6, 5, 2]) return?
What does best_gain([5, 11, 2, 7, 1, 4]) return?
In [3, 10, 1, 6], once the price 1 arrives the cheapest price becomes 1. Why is it safe to forget the 3?
What do the time and memory of best_gain grow with?
Remember
- Walk once, remembering the cheapest day behind you.
- Shortcut: carry "best start so far" and "best answer so far".
- Trap: largest minus smallest ignores the order of the days.