Foundation drill for this topic
Easy Kadane's Variant
In plain English: Find the best day to buy and the best later day to sell a stock to maximize your profit.
Track the minimum price seen so far and compute profit at each step. This is Kadane's algorithm in disguise — the max gain ending here is today's price minus the running minimum.
Prompt
Given an array prices where prices[i] is the price of a stock on the ith day, return the maximum profit you can achieve from one buy and one sell. You must buy before you sell.
Try to write it from scratch before scrolling down.
Solution
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price) # track cheapest buy
max_profit = max(max_profit, price - min_price) # best sell
return max_profit
# Test: max_profit([7,1,5,3,6,4]) == 5 (buy@1, sell@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)