Dynamic Programming - 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: You may not engage in multiple transactions simultaneously (you must sell the stock before you buy again).

Input: prices = [3, 3, 5, 0, 0, 3, 1, 4]
Output: 6
Explanation: Buy on day 4 (price=0), sell on day 6 (price=3), profit=3. Then buy on day 7 (price=1), sell on day 8 (price=4), profit=3. Total profit = 6.

Input: prices = [1, 2, 3, 4, 5]
Output: 4
Explanation: Buy on day 1 (price=1), sell on day 5 (price=5), profit=4. Total profit = 4.

We use four state variables to track the best outcomes at each stage of at most two transactions: buy1 (best after first buy), sell1 (best after first sell), buy2 (best after second buy), sell2 (best after second sell).

Initialize buy1 and buy2 to negative infinity (haven't bought yet), sell1 and sell2 to 0.
For each price: update buy1 = max(buy1, -price); sell1 = max(sell1, buy1 + price); buy2 = max(buy2, sell1 - price); sell2 = max(sell2, buy2 + price).
The answer is sell2, the maximum profit from at most two transactions.

public class BestTimeBuySellStockIII { public int maxProfit(int[] prices) { int buy1 = Integer.MIN_VALUE, sell1 = 0; int buy2 = Integer.MIN_VALUE, 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 Analysis:

Time complexity: O(n) — single pass through the prices array.
Space complexity: O(1) — only four state variables used.