Best Time to Buy and Sell Stock III
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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)
