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.

The cap of two makes this harder than either predecessor. You have to decide whether one transaction is enough or two are better, and if two, how to place two non-overlapping buy-sell windows so the combined profit is as large as possible. Greedily taking the single best transaction and then the best transaction in the leftover days fails, because the two transactions interact: one large profit can span a range that two smaller transactions would cover for a bigger combined total. With prices [1, 5, 2, 6], the best single transaction is buy at 1, sell at 6 for a profit of 5, leaving no room for a second; buying at 1, selling at 5, then buying at 2 and selling at 6 earns 8.

Any two non-overlapping transactions divide the array into a left part (days 0 to some split point) holding the first transaction and a right part (from that split point onward) holding the second. This partition, combined with precomputing the best single transaction for every prefix and every suffix, gives an O(n) solution.

Key Constraints:

Intuition

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

This reduces each split point to two questions: what is the best single transaction in days 0..i, and what is the best single transaction in days i..n-1? Trying every split point and taking the maximum sum covers every possible pair. Finding the best single transaction in a subarray is the Stock I problem: track the minimum price seen so far and the maximum profit over the scan. Doing this from scratch for every split point costs O(n) per split, O(n^2) total.

Algorithm

Example Walkthrough

Code

For each split point, the brute force recomputes both sides from scratch, even though the left subarray grows by one element each time the split point moves. The next approach precomputes the best profit for every prefix and every suffix in two linear passes, turning each split into an O(1) lookup.

Intuition

"Best single transaction in days 0..i" is the Stock I problem solved incrementally: scan left to right, track the minimum price so far and the best profit so far, and record the running answer in an array leftProfit. One O(n) pass fills every prefix. A mirror-image pass from the right, tracking the maximum price so far, fills rightProfit[i] with the best single transaction in days i..n-1.

With both arrays in hand, the answer is max(leftProfit[i] + rightProfit[i]) over all i. This prefix/suffix decomposition replaces the brute force's repeated rescans with three linear passes.

Algorithm

Example Walkthrough

Code

The O(n) time is optimal, since every price has to be examined at least once, but the two profit arrays cost O(n) extra space. The next approach replaces them with four running variables, one per transaction stage.

Intuition

Instead of splitting the array, track the states a trader can occupy while processing each day: holding nothing, holding the first stock, done with the first transaction, holding the second stock, done with both. On any day you either stay in your current state or advance to the next one, and four variables record the best running value in each non-initial state.

buy1 is the best balance after buying the first stock, which is the negative of the cheapest price so far. sell1 is the best profit after selling it. buy2 is the best balance after buying the second stock; since it is computed from sell1, the first transaction's profit offsets the cost of the second purchase. sell2 is the best total profit and becomes the answer.

Algorithm

Example Walkthrough

Code

The same recurrence extends beyond two transactions. Restating the four variables as arrays indexed by transaction number solves this problem and its k-transaction generalization with the same code.

Intuition

The four variables in Approach 3 are the k = 2 case of a general recurrence. For at most k transactions, keep two arrays: buy[j] is the best balance while holding the stock of the j-th transaction, and sell[j] is the best profit after completing j transactions. sell[0] stays 0, since zero transactions earn zero profit, and each buy[j] is funded by sell[j-1], the same chaining that connected buy2 to sell1.

For k = 2, buy[1], sell[1], buy[2], and sell[2] reproduce Approach 3 exactly. The payoff of the array form is that raising the transaction limit, which is the Stock IV problem, requires changing a single constant.

Algorithm

Example Walkthrough

This trace uses prices = [1, 2, 3, 4, 5] (Example 2), where a single transaction is optimal, to show how the recurrence handles an unused second transaction.

On a strictly rising sequence, sell[2] matches sell[1] every day: the best the second transaction can do is buy and sell at the same price, which adds nothing. The returned value of 4 comes entirely from the first transaction, buying at 1 and selling at 5.

Code