Best Time to Buy and Sell Stock III
Problem
Given daily stock prices, find the maximum profit you can make with at most two complete buy-then-sell transactions. You cannot hold more than one share at a time, so you must sell before buying again.
Examples
Constraints
- • 1 <= prices.length <= 10^5
- • 0 <= prices[i] <= 10^5
Hints & approach
Hint 1
Model the day-by-day state you are in: before first buy, holding first, sold first, holding second, sold second.
Hint 2
Each state's best value comes from staying put or transitioning from the previous state.
Hint 3
Four variables updated in order each day are enough.
Approachtry the hints first
Track four running maxima: buy1 (best balance after the first buy), sell1, buy2 and sell2. For each price p, update buy1 = max(buy1, -p), sell1 = max(sell1, buy1 + p), buy2 = max(buy2, sell1 - p) and sell2 = max(sell2, buy2 + p). Start the buys at negative infinity and the sells at 0. sell2 is the answer, and the same state machine generalises to k transactions.
Time O(n) · Space O(1)