Best Time to Buy and Sell Stock
Find the maximum profit from one buy and one sell.
Pattern fit
The cleanest view is to track the best buying point so far and ask whether selling today beats the current answer.
Key observation
At each day the only historical information that matters is the minimum price seen before today.
Target complexity
O(n) / O(1)
How to break down the solution cleanly
The cleanest view is to track the best buying point so far and ask whether selling today beats the current answer.
At each day the only historical information that matters is the minimum price seen before today.
Name the state in plain language.
List the decisions that can transition into the state.
Reference implementation
Python# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = transition(dp, i)
# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = transition(dp, i, j)
Common pitfalls
Allowing sell before buy by updating minimum price in the wrong order.
Treating it as multiple transactions.
Common follow-ups
How would multiple transactions change the model?
Can you explain this as a rolling DP state?
Continue with related problems
Build repeatable depth inside the Dynamic Programming cluster before moving on.