Best Two Stock Trades

hard dp stocks

Problem

Given daily stock prices, you may complete at most two non-overlapping buy-sell trades. Return the maximum total profit.

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;
}

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