Maximum profit by buying and selling a share at most twice

The problem, simply

You get prices, the price of a share on each day. You may do at most two trades. A trade is one buy and then one later sell. You can hold only one share at a time, so the second buy must come after the first sell.

Give back the most money you can make. Doing nothing (0) is always allowed.

A story to remember it

Picture it

Examples

Way 1: the simple way

Two trades never overlap, so there is a day that splits them: the first trade lives on the left, the second on the right. Try every split day.

1. For each split day i, find the best single trade inside days 0..i: track the lowest price so far.
2. Find the best single trade inside days i..n-1: walk from the right and track the highest price so far.
3. Add the two. Keep the biggest sum over all splits.

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

How long it takes: n splits, and each one walks the whole list, O(n^2). Extra room: a few numbers, O(1). You can make this O(n) with two helper arrays, one for the best left trade up to each day and one for the best right trade from each day.

Way 2: the clever way

Keep the four piggy banks as four numbers. Money spent counts as negative.

1. buy1: most money after the first buy. Start at minus infinity (not bought yet).
2. sell1: most money after the first sell. Start at 0.
3. buy2: most money after the second buy. Start at minus infinity.
4. sell2: most money after the second sell. Start at 0.

Every day, with price p, update them in this order:

• buy1 = max(buy1, -p)
• sell1 = max(sell1, buy1 + p)
• buy2 = max(buy2, sell1 - p)
• sell2 = max(sell2, buy2 + p)

The table below is the full DP table these four numbers stand for: one row per bank, one column per day. Each box comes from the box on its left (do nothing today) and the box above it (do this step today). The code only keeps the newest column.

class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE, sell1 = 0;   // first trip
        int buy2 = Integer.MIN_VALUE, sell2 = 0;   // second trip
        for (int p : prices) {
            buy1 = Math.max(buy1, -p);             // buy for the first time today
            sell1 = Math.max(sell1, buy1 + p);     // or sell the first share today
            buy2 = Math.max(buy2, sell1 - p);      // or buy again with the profit
            sell2 = Math.max(sell2, buy2 + p);     // or sell the second share today
        }
        return sell2;
    }
}

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

Watch out for

• Buying and selling on the same day is allowed by the updates, but it earns 0, so it never changes the answer.
• sell2 already covers "only one trade" and "no trade", because buy2 can be sell1 - p with the same p that was just sold at.
• Do not pick the two biggest single rises. In [1, 2, 4, 2, 5, 7, 2, 4, 9, 0] the best is 13 (1 to 7, then 2 to 9). The two biggest separate rises, 2 to 7 and 2 to 9, make only 12.

What interviewers ask next

• At most k trades? Use arrays buy[1..k] and sell[1..k] with the same rules, O(n * k).
• As many trades as you like? Add up every rise from one day to the next.
• With a cooldown day after selling, or a fee per trade? Same piggy bank idea with one more bank or a fee subtracted on each sell.
• Return the actual buy and sell days. Remember the day each bank last improved, plus the day of the bank before it at that moment.

Remember this

Grown-up words: the piggy banks are states, the chain of updates is a state machine DP, minus infinity means an impossible state, and the split day idea is a prefix and suffix best trade.