Best Time to Buy and Sell Stock III

hard dp stocks

Problem

You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete at most two transactions.

Inputprices = [3,3,5,0,0,3,1,4]

Output6

Track four running quantities: best cost after first buy (b1), best profit after first sell (s1), best cost after second buy net of s1 (b2), best profit after second sell (s2).

prices

def max_profit(prices):
    b1 = b2 = float('inf')
    s1 = s2 = 0
    for p in prices:
        b1 = min(b1, p)
        s1 = max(s1, p - b1)
        b2 = min(b2, p - s1)
        s2 = max(s2, p - b2)
    return s2

function maxProfit(prices) {
  let b1 = Infinity, b2 = Infinity, s1 = 0, s2 = 0;
  for (const p of prices) {
    b1 = Math.min(b1, p);
    s1 = Math.max(s1, p - b1);
    b2 = Math.min(b2, p - s1);
    s2 = Math.max(s2, p - b2);
  }
  return s2;
}

class Solution {
    public int maxProfit(int[] prices) {
        int b1 = Integer.MAX_VALUE, b2 = Integer.MAX_VALUE;
        int s1 = 0, s2 = 0;
        for (int p : prices) {
            b1 = Math.min(b1, p);
            s1 = Math.max(s1, p - b1);
            b2 = Math.min(b2, p - s1);
            s2 = Math.max(s2, p - b2);
        }
        return s2;
    }
}

int maxProfit(vector<int>& prices) {
    int b1 = INT_MAX, b2 = INT_MAX, s1 = 0, s2 = 0;
    for (int p : prices) {
        b1 = min(b1, p);
        s1 = max(s1, p - b1);
        b2 = min(b2, p - s1);
        s2 = max(s2, p - b2);
    }
    return s2;
}

Explanation

We may do at most two buy-sell trades. The slick trick is to track four running numbers as we sweep the prices once, each representing the best we can do after a certain step of the two-trade story.

b1 = the lowest price paid for the first buy so far. s1 = the best profit after the first sell. b2 = the effective cost of the second buy after reinvesting the first profit. s2 = the best total profit after the second sell.

For each price p we update them in order: b1 = min(b1, p), then s1 = max(s1, p - b1), then b2 = min(b2, p - s1), then s2 = max(s2, p - b2). Because b2 subtracts s1, the second trade's cost is discounted by the money the first trade already earned, which is what chains the two trades together.

The answer is simply s2 at the end. Doing one trade or zero is automatically covered because the maxes never force you to trade twice.

Example: prices = [3,3,5,0,0,3,1,4]. The first trade buys at 0 and sells at 3 (+3), the second buys at 1 and sells at 4 (+3), giving s2 = 6.

Time: O(n) Space: O(1)