Best Time to Buy and Sell Stock

1. The obvious way

   Try every buy day with every later sell day: O(n²).

2. The key insight

   If you sell today, the best purchase is the lowest price so far. So walk through the days keeping the lowest price seen and the best profit found: each day first check "today minus lowest", then update the lowest.

3. The algorithm
   1. Sticky note 1: lowest price so far (start very high). Sticky note 2: best profit (start 0).
   2. For each day: profit if sold today = today's price minus the lowest. Keep it if it beats the best.
   3. Then, if today is cheaper than the lowest, update the lowest.
   4. After the last day the best profit is the answer (0 if prices only fall).

Watch it run

lowest 7, best profit 0

def max_profit(prices):
    lowest = float("inf")            # cheapest price seen so far
    best = 0                         # best profit seen so far
    for price in prices:
        best = max(best, price - lowest)     # sell today?
        lowest = min(lowest, price)          # is today the cheapest day yet?
    return best

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.