DSA problem
Best Time to Buy and Sell Stock III
You are given an array prices where prices[i] is the price of a given stock on the i-th day. Find the maximum profit you can achieve. You may complete at most two transactions. Note that you cannot engage in multiple transactions simultaneously — you must sell the stock before you buy again.
The clean way to think about this problem is as a small finite state machine that the trader walks through in order: start with no stock, buy a first time, sell a first time, buy a second time, sell a second time. Each prices[i] triggers one round of transitions where each state asks "should I move forward from my predecessor on this day, or stay put?". Greedy approaches like collecting all local profit peaks break the at-most-two constraint, so we need explicit state tracking.
A straightforward DP defines dp[k][i] as the maximum profit using at most k transactions through day i, with recurrence dp[k][i] = max(dp[k][i-1], prices[i] + max_{j<=i}(dp[k-1][j-1] - prices[j])). That is O(n) per state if implemented carefully, O(n) total for fixed k = 2, but it requires care to keep max(dp[k-1][j-1] - prices[j]) in a running variable rather than a nested loop.
The optimal formulation collapses everything into four rolling scalars: buy1, sell1, buy2, sell2. buy1 is the best profit after the first buy (so a non-positive number, the negation of the price paid), sell1 is the best profit after the first sell, and so on. Each new price triggers four max updates in fixed order. The answer is sell2 at the end. This runs in O(n) time and O(1) space and generalizes naturally to k transactions.
Examples
prices = [3,3,5,0,0,3,1,4]6prices = [1,2,3,4,5]4prices = [7,6,4,3,1]0Constraints
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^5
- You may complete at most two transactions.
- You must sell before you buy again (no simultaneous holdings).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.