Best Time to Buy and Sell Stock
EasySliding window
prices[i] is the price of a stock on day i. You may buy once and sell once, on a later day.
Return the largest profit you can make. If no trade makes money, return 0.
Examples
Input: prices = [8, 3, 6, 1, 5, 4] Output: 4
Buy on day 3 at 1 and sell on day 4 at 5.
Input: prices = [9, 7, 4, 1] Output: 0
The price only falls, so the best choice is not to trade.
Constraints
1 ≤ prices.length ≤ 10⁵0 ≤ prices[i] ≤ 10⁴
Stuck?
Hint 1
On any day, the best sale is that day’s price minus the lowest price before it.
Hint 2
Keep the lowest price so far and the best profit so far, in one pass.
The idea
If you sell on a given day, the best day to have bought is the cheapest day before it. So walk the prices once, keeping the lowest price so far, and each day work out what selling that day would earn.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
lowest starts at Infinity, so the first price replaces it. best starts at 0, the answer when no trade makes money, since not trading is always allowed.
function maxProfit(prices) { let lowest = Infinity; let best = 0; for (const price of prices) { lowest = Math.min(lowest, price); best = Math.max(best, price - lowest); } return best;}The trap
Subtracting the lowest price from the highest finds the widest gap in the list, which is the answer when prices rise steadily. It ignores the order of the days: when the highest price comes before the lowest, it sells before it buys. Prices that only fall give a profit where the answer is 0.
function maxProfit(prices) { return Math.max(...prices) - Math.min(...prices); // ignores that you buy before you sell}