Best Time to Buy and Sell Stock
Easy · rating 1000 · arrays, dp
The first line contains n. The second line contains n integers, the stock price on each day. You may buy once and sell once (sell after buy). Print the maximum profit achievable, or 0 if no profit is possible.
Editorial
Approach
You want the largest price[j] − price[i] with j > i. A single pass suffices: track the minimum price seen so far, and at each day compute the profit if you sold today (today's price minus that running minimum), keeping the best.
Why one pass works
The best sell day only depends on the cheapest buy day before it. By carrying the running minimum forward, every day already knows the optimal buy price to its left, so no nested loop is needed.
min_price = infinity
best = 0
for p in prices:
min_price = min(min_price, p)
best = max(best, p - min_price)
return bestComplexity
Time: O(n). Space: O(1).