Back to solutions

Best Time to Buy and Sell Stock III

HardDynamic Programming

Maximize profit with at most two buy-sell transactions, where you must sell before buying again.

Open problem
Constraints
  • 1 <= n <= 10^5
  • 0 <= prices[i] <= 10^5

Four running states

Time O(n)Space O(1)

Track the best values after the first buy, first sell, second buy, and second sell as you scan. Each state updates from the previous, capturing at most two transactions in O(1) space.

#include <bits/stdc++.h>
using namespace std;

int maxProfit(vector<int>& prices) {
    int buy1 = INT_MIN, sell1 = 0, buy2 = INT_MIN, sell2 = 0;
    for (int p : prices) {
        buy1 = max(buy1, -p);
        sell1 = max(sell1, buy1 + p);
        buy2 = max(buy2, sell1 - p);
        sell2 = max(sell2, buy2 + p);
    }
    return sell2;
}