You are given an array where each element represents the price of a stock on a given day. Your task:

Find the maximum profit achievable with at most TWO buy-and-sell transactions.

Rules:

• You must sell before buying again
• You may complete one, two, or zero transactions
• Only one stock can be held at a time

Example:

Input:  [3,3,5,0,0,3,1,4]
Output: 6
Explanation:
Buy at 3, sell at 5 → profit = 2
Buy at 0, sell at 4 → profit = 4
Total profit = 6

---

Problem Understanding

This is an extension of earlier stock problems:

Problem	Allowed Transactions
121	1 transaction
122	unlimited
123	at most 2

The trick:

• You must determine the optimal split of the timeline into two profitable segments
• You cannot brute force all splits (too slow)

---

Logic Explained in Simple English

To think about this problem intuitively:

1. The first transaction must occur somewhere in the earlier part of the price list.
2. The second transaction must occur afterward.
3. We want the best first profit and best second profit that do not overlap.

The most efficient way:

• Make one pass computing the best profit up to each day
• Make another pass computing the best profit from each day to the end
• Add the two results per day to determine the best combined total

So we build:

left[i]  = max profit from day 0 to i
right[i] = max profit from day i to last

Then:

answer = max(left[i] + right[i])

This ensures:

• The two transactions do not overlap
• Every possible dividing point is evaluated

---

Step-by-Step Approach

Phase 1 — Compute best profit up to each day (left array)

1. Track minimum price seen so far
2. For each day compute: left[i] = max(left[i-1], prices[i] - minPrice)

Phase 2 — Compute best profit from each day onward (right array)

1. Track maximum price seen from the right
2. For each day going backward compute: right[i] = max(right[i+1], maxPrice - prices[i])

Phase 3 — Combine results

For each i:

maxProfit = max(maxProfit, left[i] + right[i])

---

Java Implementation

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        
        int n = prices.length;
        int[] left = new int[n];
        int[] right = new int[n];
        
        int minPrice = prices[0];
        for (int i = 1; i < n; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            left[i] = Math.max(left[i-1], prices[i] - minPrice);
        }
        
        int maxPrice = prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            maxPrice = Math.max(maxPrice, prices[i]);
            right[i] = Math.max(right[i+1], maxPrice - prices[i]);
        }
        
        int maxProfit = 0;
        for (int i = 0; i < n; i++) {
            maxProfit = Math.max(maxProfit, left[i] + right[i]);
        }
        
        return maxProfit;
    }
}

---

Dry Run Example

Input:

[3,3,5,0,0,3,1,4]

Build left[]

Track min price and best profit up to each day:

Day:   0 1 2 3 4 5 6 7
Price: 3 3 5 0 0 3 1 4
left:  0 0 2 2 2 3 3 4

Meaning:

• Best single transaction profit up to each day

Build right[]

Track max price from right:

Day:    0 1 2 3 4 5 6 7
Price:  3 3 5 0 0 3 1 4
right:  4 4 4 4 4 3 3 0

Meaning:

• Best single transaction profit starting from each day

Combine

Add left[i] + right[i]:

i=0 → 0+4 = 4
i=1 → 0+4 = 4
i=2 → 2+4 = 6
i=3 → 2+4 = 6
i=4 → 2+4 = 6
i=5 → 3+3 = 6
i=6 → 3+3 = 6
i=7 → 4+0 = 4

Final answer:

6

---

Time and Space Complexity

Time Complexity

O(n)

Two passes left-to-right and right-to-left

Space Complexity

O(n)

Two extra arrays

---

Common Mistakes and How to Avoid Them

Mistake 1: Trying to brute force all split points

This leads to O(n²)

Mistake 2: Confusing with Problem 122 (unlimited trades)

This problem only allows two

Mistake 3: Forgetting transactions must not overlap

You must sell before buying again

Mistake 4: Using greedy logic

Greedy fails because profit dips may appear before second rise

Mistake 5: Using DP with unnecessary complexity

Some DP solutions are overengineered