Problem
Given stock prices, find max profit from at most TWO transactions. You can’t hold more than one stock at a time.
Example
Input: [3,3,5,0,0,3,1,4]
Output: 6
Buy 0, sell 3; buy 1, sell 4.Solution
Track 4 states: buy1, sell1, buy2, sell2. Each is the best balance after each transaction step.
def max_profit(prices):
buy1 = buy2 = float('-inf')
sell1 = sell2 = 0
for price in prices:
buy1 = max(buy1, -price)
sell1 = max(sell1, buy1 + price)
buy2 = max(buy2, sell1 - price)
sell2 = max(sell2, buy2 + price)
return sell2function maxProfit(prices) {
let buy1 = -Infinity, buy2 = -Infinity;
let sell1 = 0, sell2 = 0;
for (const price of prices) {
buy1 = Math.max(buy1, -price);
sell1 = Math.max(sell1, buy1 + price);
buy2 = Math.max(buy2, sell1 - price);
sell2 = Math.max(sell2, buy2 + price);
}
return sell2;
}int maxProfit(vector<int>& prices) {
int buy1 = INT_MIN, buy2 = INT_MIN;
int sell1 = 0, sell2 = 0;
for (int price : prices) {
buy1 = max(buy1, -price);
sell1 = max(sell1, buy1 + price);
buy2 = max(buy2, sell1 - price);
sell2 = max(sell2, buy2 + price);
}
return sell2;
}public int maxProfit(int[] prices) {
int buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
int sell1 = 0, sell2 = 0;
for (int price : prices) {
buy1 = Math.max(buy1, -price);
sell1 = Math.max(sell1, buy1 + price);
buy2 = Math.max(buy2, sell1 - price);
sell2 = Math.max(sell2, buy2 + price);
}
return sell2;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
State machine: each variable holds the best profit/balance you could have at that “step” by today. Order matters — we use buy1 before updating sell1, etc.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?