Best Time to Buy and Sell Stock III

Share

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).

Example 1
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.
Example 2
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.

Solution Approach - State Machine DP

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.
Java
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.