Dynamic Programming • State Tracking

Best Time to Buy and Sell Stock

Track the minimum price seen so far to find the maximum possible profit from a single transaction.

Overview

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Keep track of the minimum price encountered so far. This allows computing the maximum profit if we sell on the current day.

If current price is less than min_price, update min_price. Otherwise, check if current price - min_price is greater than max_profit.

We only need a single pass (O(N) time) because the best buy day for any given sell day is always the minimum price seen before it.

Day 17

Day 21

Day 35

Day 43

Day 56

Day 64

Code Tracker

:::

1let minPrice = Infinity; let maxProfit = 0;

2for (let price of prices) {

3 if (price < minPrice) minPrice = price;

4 else if (price - minPrice > maxProfit)

5 maxProfit = price - minPrice;

6}