Maximum profit by buying and selling a share at most twice [IMP]

Problem Statement

You are given an array prices[] where prices[i] is the price of a stock on day i. You can complete at most two transactions (buy and sell). You must sell before buying again. Find the maximum profit you can achieve.

Example:

• 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. Buy on day 7 (price=1), sell on day 8 (price=4), profit=3. Total profit = 6.

Noob-Friendly Explanation

Imagine you're trading stocks and you get to see all future prices (like having a crystal ball!). The catch: you can only make at most 2 round trips (buy then sell = 1 trip). You want to maximize your total earnings from these two trades.

Think of it like going shopping twice. You buy low and sell high, twice. You need to find the two best buy-low-sell-high opportunities in the price list.

Approach 1: Brute Force

Intuition

Split the array into two parts at every possible split point. Find the maximum profit from one transaction in the left part and one transaction in the right part. The total is the maximum sum across all split points.

Algorithm

1. For each split point i, compute the max profit from prices[0..i] and prices[i..n-1].
2. For each part, find the max profit by tracking min price and max profit.
3. Return the maximum total across all splits.

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) return 0;

        int maxProfit = 0;

        for (int i = 0; i < n; i++) {
            // Max profit from one transaction in left part [0..i]
            int leftProfit = 0, minLeft = prices[0];
            for (int j = 1; j <= i; j++) {
                minLeft = Math.min(minLeft, prices[j]);
                leftProfit = Math.max(leftProfit, prices[j] - minLeft);
            }

            // Max profit from one transaction in right part [i..n-1]
            int rightProfit = 0, maxRight = prices[n - 1];
            for (int j = n - 2; j >= i; j--) {
                maxRight = Math.max(maxRight, prices[j]);
                rightProfit = Math.max(rightProfit, maxRight - prices[j]);
            }

            maxProfit = Math.max(maxProfit, leftProfit + rightProfit);
        }

        return maxProfit;
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - For each split point, we scan left and right parts.
• Space Complexity: O(1) - Only a few variables used.

Approach 2: Optimal (State Machine DP)

Intuition

Track four states as we scan through prices:

1. buy1: Max profit after first buy (most negative cost).
2. sell1: Max profit after first sell.
3. buy2: Max profit after second buy.
4. sell2: Max profit after second sell.

We update these states greedily in a single pass.

Algorithm

1. Initialize buy1 = -infinity, sell1 = 0, buy2 = -infinity, sell2 = 0.
2. For each price:
   • buy1 = max(buy1, -price) — best we can do after buying once.
   • sell1 = max(sell1, buy1 + price) — best after selling once.
   • buy2 = max(buy2, sell1 - price) — best after buying second time.
   • sell2 = max(sell2, buy2 + price) — best after selling second time.
3. Return sell2.

class Solution {
    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 variables used.