#123
Best Time to Buy and Sell Stock III
Hard State machine DP (2 transactions)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Make at most two buy-sell transactions (not overlapping). Return the maximum profit.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: at most two trades.
Why this works: four states in a chain: after buy 1, after sell 1, after buy 2, after sell 2.
Example: [3, 3, 5, 0, 0, 3, 1, 4]
buy 0 sell 3 (+3), buy 1 sell 4 (+3) → 6✦Hints open one at a time
Track four states: after first buy, after first sell, after second buy, after second sell.
Each state builds on the previous one in the chain.
↗Approach
For each price: buy1 = max(buy1, −p), sell1 = max(sell1, buy1 + p), buy2 = max(buy2, sell1 − p), sell2 = max(sell2, buy2 + p). Answer sell2.
</>Solution (Java)
class Solution {
public int maxProfit(int[] prices) {
int buy1 = Integer.MIN_VALUE, sell1 = 0, buy2 = Integer.MIN_VALUE, sell2 = 0;
for (int p : prices) {
buy1 = Math.max(buy1, -p);
sell1 = Math.max(sell1, buy1 + p);
buy2 = Math.max(buy2, sell1 - p); // second buy uses first profit
sell2 = Math.max(sell2, buy2 + p);
}
return sell2;
}
}!Common mistake
Splitting the array at every point and running the one-transaction solution on both sides each time — O(n²).
Complexity
- Time: O(n).
- Space: O(1).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon