Foundation drill for this topic
Easy Greedy Choice
In plain English: Find the best day to buy and the best day to sell a stock to make the most money.
Track the minimum price seen so far. At each day, the best you can do is sell at today's price minus the cheapest buy — one pass, O(1) space.
Prompt
Given an array of stock prices (one per day), find the maximum profit from one buy and one sell (buy before sell).
Try to write it from scratch before scrolling down.
Solution
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for p in prices:
min_price = min(min_price, p)
max_profit = max(max_profit, p - min_price) # sell today, bought at min
return max_profit
# Test: max_profit([7,1,5,3,6,4]) == 5 (buy at 1, sell at 6)
# Test: max_profit([7,6,4,3,1]) == 0 (no profit possible)Quick recall drills to reinforce this pattern.
Two-state DP: cash (free to buy) and hold (free to sell). Fee paid on sell. No cooldown needed.
def maxProfit(prices, fee):
cash = 0 # not holding
hold = -prices[0] # holding
for p in prices[1:]:
cash = max(cash, hold + p - fee)
hold = max(hold, cash - p)
return cashThree-state machine: hold → sell → rest → buy. After selling, must rest one day before buying.
def maxProfit(prices):
hold = -prices[0] # holding stock
sold = 0 # just sold (cooldown next)
rest = 0 # not holding, free to buy
for p in prices[1:]:
hold, sold, rest = (
max(hold, rest - p), # keep or buy
hold + p, # sell
max(rest, sold), # stay or come off cooldown
)
return max(sold, rest)Single-pass tracking of running minimum and maximum profit. Classic greedy O(n) solution.
mn = float('inf')
mx = 0
for p in prices:
mn = min(mn, p)
mx = max(mx, p - mn)