Maximum profit by buying and selling a share atmost twice

The problem, simply

You get the price of one share for each day, in order. You may do at most two trades. A trade is: buy one share on some day, then sell it on a later day. You may hold only one share at a time, so you must sell the first share before you buy the second.

Give back the biggest total profit. If no trade earns money, the answer is 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

Two trades never overlap, so there is a day i that splits the week: the first trade happens on days 0..i and the second on days i..n-1. Try every split day, and for each half find the best single trade.

1. For each split day i, find the best one trade in prices[0..i]: walk left to right, remember the lowest price so far, and check today minus that lowest.
2. Do the same for prices[i..n-1].
3. Add the two and keep the biggest total.

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int best = 0;
        for (int i = 0; i < n; i++) {               // the split day
            int left = 0, low = prices[0];
            for (int j = 1; j <= i; j++) {           // best trade on days 0..i
                low = Math.min(low, prices[j]);
                left = Math.max(left, prices[j] - low);
            }
            int right = 0;
            low = prices[i];
            for (int j = i + 1; j < n; j++) {        // best trade on days i..n-1
                low = Math.min(low, prices[j]);
                right = Math.max(right, prices[j] - low);
            }
            best = Math.max(best, left + right);
        }
        return best;
    }
}

How long it takes: for each of the n split days we walk the whole week, O(n^2). Extra room: a few numbers, O(1).

Way 2: the clever way

Keep the four pocket notes from the story. Money you spend counts as negative, so buying at price 3 leaves -3 in your pocket.

• buy1: best pocket after the first buy. It starts at minus infinity, because you cannot be holding a share before you buy one.
• sell1: best pocket after the first sell. Starts at 0.
• buy2: best pocket after the second buy. Starts at minus infinity.
• sell2: best pocket after the second sell. Starts at 0.

Each morning, with price p, update them in this order:

1. buy1 = max(buy1, -p): keep the old buy, or buy today.
2. sell1 = max(sell1, buy1 + p): keep the old sell, or sell today.
3. buy2 = max(buy2, sell1 - p): buy the second share today with the money from trade one.
4. sell2 = max(sell2, buy2 + p): sell the second share today.

The table below is the real thing the code computes: one column per day, one row per note. Orange cells changed today; black cells kept yesterday's value.

class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE, sell1 = 0;   // first trade
        int buy2 = Integer.MIN_VALUE, sell2 = 0;   // second trade
        for (int p : prices) {
            buy1 = Math.max(buy1, -p);           // buy the first share today?
            sell1 = Math.max(sell1, buy1 + p);   // sell it today?
            buy2 = Math.max(buy2, sell1 - p);    // buy the second with trade one's money?
            sell2 = Math.max(sell2, buy2 + p);   // sell the second today?
        }
        return sell2;
    }
}

How long it takes: one walk over the days, O(n). Extra room: four numbers, O(1). The table in the animation is only for the picture; the code keeps only the last column.

Another way: best on the left plus best on the right

This is Way 1 made fast. Instead of recomputing each half for every split day, fill two tables once.

1. left[i] is the best single trade using days 0..i. Walk forward, remember the lowest price so far.
2. right[i] is the best single trade using days i..n-1. Walk backward, remember the highest price so far.
3. The answer is the biggest left[i] + right[i].

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) return 0;
        int[] left = new int[n];
        int low = prices[0];
        for (int i = 1; i < n; i++) {
            low = Math.min(low, prices[i]);
            left[i] = Math.max(left[i - 1], prices[i] - low);
        }
        int[] right = new int[n];
        int high = prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            high = Math.max(high, prices[i]);
            right[i] = Math.max(right[i + 1], high - prices[i]);
        }
        int best = 0;
        for (int i = 0; i < n; i++) best = Math.max(best, left[i] + right[i]);
        return best;
    }
}

This is O(n) time and O(n) room. It is easier to explain on a whiteboard, and it is a good stepping stone to the four notes.

Watch out for

• Picking the best single trade first and then the best trade in what is left fails on [1, 2, 4, 2, 5, 7, 2, 4, 9, 0].
• Starting buy1 at 0 instead of minus infinity pretends you got a free share before day 0.
• Fewer than two days: return 0. The four notes handle this on their own.

What interviewers ask next

• At most k trades. Keep buy[j] and sell[j] for j = 1..k, updated the same way: buy[j] = max(buy[j], sell[j-1] - p). That is O(n k). If k >= n / 2, it is the same as unlimited trades.
• Unlimited trades. Add up every rise from one day to the next.
• A cooldown day after each sell. Keep three notes: holding, just sold, and resting. When you buy, use yesterday's resting money.
• A fee per trade. Unlimited trades, and subtract the fee when you sell.
• Why is this dynamic programming? Each note is the best answer for a small question (best pocket after so many actions by today), and today's answer comes only from yesterday's.

Remember this

Grown-up words: a trade is a transaction, the four notes are dynamic programming states (a small state machine), the split-day idea is prefix and suffix best profit, and minus infinity is the "impossible" starting value.