This is the third problem in the "Best Time to Buy and Sell Stock" series, and it introduces a specific constraint: at most two transactions. In Stock I, you could make one transaction. In Stock II, you had unlimited transactions. Here, you are capped at two.

Why does limiting it to two make things harder? Because now you need to decide where to "split" your effort. Should you use both transactions, or is one enough? If you use both, how do you pick two non-overlapping buy-sell windows that maximize the combined profit? You cannot just find the single best transaction and then find the second best in the remaining days, because the two transactions might interact. For example, one large profit might span a range where two smaller but better-combined profits exist.

The key observation is that any two non-overlapping transactions divide the array into a "left transaction" (days 0 to some split point) and a "right transaction" (from that split point onward). This partitioning idea, combined with the fact that we can precompute the best single transaction from the left and right, leads to an elegant O(n) solution.

Key Constraints:

Intuition

The most straightforward way to think about two transactions is: any valid pair of transactions can be separated by a split point. The first transaction happens entirely within days 0 to i, and the second happens entirely within days i to n-1 (they can share the boundary day since selling and buying on the same day is a no-op).

So if we could quickly answer "what is the best single transaction in days 0..i?" and "what is the best single transaction in days i..n-1?", we could try every split point and pick the maximum sum. Finding the best single transaction in a subarray is the classic Stock I problem: track the minimum price seen so far and the maximum profit. But doing this from scratch for every split point would be O(n) per split, giving O(n^2) total.

Algorithm

Example Walkthrough

Code

For each split point, we recompute the best single transaction on each side from scratch. But the left subarray only grows by one element as we move the split point. What if we precomputed the best left and right profits so that evaluating each split becomes O(1)?

Intuition

The brute force recomputes the best single transaction for every split point. But notice that "best single transaction in days 0..i" is just the Stock I problem solved incrementally. As we scan left to right, we track the minimum price so far and the best profit so far. We can store the answer for every prefix in an array leftProfit[i] in a single O(n) pass.

Similarly, the "best single transaction in days i..n-1" can be computed by scanning right to left, tracking the maximum price so far, stored in rightProfit[i].

Once we have both arrays, the answer is simply max(leftProfit[i] + rightProfit[i]) for all i.

Algorithm

Example Walkthrough

Code

The O(n) time is already optimal, but we are using O(n) extra space. Can we track all possible stages of the two transactions simultaneously using only a constant number of variables?

Intuition

Instead of splitting the array, think about the states you can be in as you process each day: before any transaction, after first buy, after first sell, after second buy, after second sell. At each day, you can either stay in your current state or move to the next one. We track the best profit achievable in each state using four variables.

The elegant part: buy1 tracks the minimum cost of the first buy. sell1 tracks the best profit after completing the first transaction. buy2 builds on sell1, effectively using the first transaction's profit as a "discount" for the second buy. And sell2 tracks the final answer.

Algorithm

Example Walkthrough

Code