Best time to buy and Sell stock

The problem, simply

You get a list of prices. prices[i] is the price of one thing on day i. You may buy it once and sell it once, and you must buy before you sell.

Give back the most money you can earn. If prices only go down, you should not trade at all, so the answer is 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every pair of days. For each buy day, try every later sell day, and keep the biggest gain.

1. Set best = 0.
2. For each buy day i, and each sell day j after it, compute prices[j] - prices[i].
3. If it is bigger than best, keep it.

class Solution {
    public int maxProfit(int[] prices) {
        int best = 0;
        for (int i = 0; i < prices.length; i++) {          // buy day
            for (int j = i + 1; j < prices.length; j++) {  // a later sell day
                best = Math.max(best, prices[j] - prices[i]);
            }
        }
        return best;
    }
}

How long it takes: about n * n / 2 pairs of days, so O(n^2). Extra room: two counters, O(1). With a hundred thousand days this is billions of steps, too slow.

Way 2: the clever way

If you sell on day j, the best buy day is the cheapest day before j. So you never need to look back. Walk forward once and carry two numbers:

• cheapest: the lowest price seen so far.
• best: the biggest gain seen so far.

1. Start with cheapest as a huge number and best = 0.
2. For each price: first update cheapest if today is lower.
3. Then compute price - cheapest, the gain from selling today, and update best.

class Solution {
    public int maxProfit(int[] prices) {
        int cheapest = Integer.MAX_VALUE;  // lowest price seen so far
        int best = 0;                      // most money earned so far
        for (int price : prices) {
            cheapest = Math.min(cheapest, price);          // maybe a new cheapest day
            best = Math.max(best, price - cheapest);       // sell today?
        }
        return best;
    }
}

How long it takes: one walk over the days, O(n). Extra room: two numbers, O(1).

There is a second way to see it. Write down how much the price moves each day: [-6, 4, -2, 3, -2]. Holding the sticker from day i to day j earns the sum of the moves in between. So the answer is the biggest sum of a run of moves, which is exactly Kadane's trick from the maximum subarray problem.

Watch out for

• Start best at 0, not at a negative number. Not trading is always allowed.
• An empty array or one price must return 0, not crash.
• Update cheapest before computing today's gain, or after. Both work here, because selling on the same day earns 0. Mixing up which price you subtract from which does not work.

What interviewers ask next

• Return the buy and sell days too. Remember the index of cheapest, and save both days whenever best grows.
• Buy and sell as many times as you like. Add up every upward step: sum of max(0, prices[i] - prices[i-1]).
• At most two trades. Keep four numbers: best after first buy, first sell, second buy, second sell, and update them each day. O(n) time.
• At most k trades, a waiting day after selling, or a fee per trade. All are small state machines: a few numbers updated each day, one per state.
• Why is the greedy walk correct? For each sell day the only buy day that matters is the cheapest earlier one, and we hold exactly that.

Remember this

Grown-up words: the note in your pocket is a running minimum (prefix minimum), the daily moves are price differences, and finding the best run of moves is Kadane's algorithm for maximum subarray sum.