26. Maximum Profit by Buying and Selling a Share at Most Twice

Given the price of a stock on each of n days, find the maximum total profit achievable using at most two non-overlapping buy-sell transactions (a new buy must happen after the previous sell). Print that maximum profit.

Input: The first line contains n, the number of days. The second line contains n space-separated integers representing the stock price on each day. Output: Print a single integer - the maximum total profit achievable with at most two non-overlapping buy-sell transactions.

1 <= n <= 10^5

The two transactions must be genuinely non-overlapping (the second buy strictly after the first sell) - the split-point technique automatically enforces this, since the left scan and right scan never share the same day's transaction.

Same stock-profit idea as before, but now you're allowed up to TWO separate buy-then-sell rounds (the second buy must happen after the first sell). Maximize your combined profit. Brute force: Try every possible pair of non-overlapping buy-sell-buy-sell combinations directly - this quickly becomes an enormous number of combinations to check, far too slow for any realistic input size. Optimised: By precomputing 'best single transaction profit up to day i' and 'best single transaction profit from day i onward' as two separate arrays (each computable in one linear pass, reusing the exact single-transaction technique from the previous lesson), you can combine them at every possible split point in constant time per split - turning an exponential search into two linear scans plus one linear combination step.

For every possible split index i (the day the first transaction's window ends and the second begins), compute the best single-transaction profit achievable entirely within prices[0..i] and, separately, the best single-transaction profit achievable entirely within prices[i..n-1], each with its own O(n) single pass over that sub-range (tracking a running minimum price and best profit so far), then add the two together. Taking the best split point i gives the correct answer for at most two transactions, but redoing an O(n) scan for every one of the n split points makes this quadratic overall. Time: O(n^2) Space: O(1) extra (excluding output)

Directly try every choice of buy1 < sell1 < buy2 < sell2 index quadruple, computing the profit (prices[sell1]-prices[buy1]) + (prices[sell2]-prices[buy2]) for each valid ordering and keeping the maximum found. This is a literal translation of 'at most two non-overlapping transactions' and is guaranteed correct, but four nested index choices make it far too slow for n up to 10^5. Time: O(n^4) Space: O(1)

Instead of recomputing a single-transaction scan for every split point, precompute it once for all split points in two linear passes: a forward pass builds an array where forward[i] is the best single-transaction profit achievable using only prices[0..i], updating a running minimum price as it goes; a backward pass builds backward[i] as the best single-transaction profit achievable using only prices[i..n-1], updating a running maximum price from the right. The answer is then the maximum over all i of forward[i] + backward[i], reusing the same prefix/suffix idea as the better approach but computing every split point's pieces in one shared linear sweep each instead of recomputing them from scratch. Time: O(n) Space: O(n)

1. Scan left to right, computing the best possible profit from a SINGLE transaction completed by or on each day. 2. Scan right to left, computing the best possible profit from a SINGLE transaction starting from each day onward. 3. For every possible 'split day' (finish the first transaction here, start the second one right after), add the left-scan's value up to that day and the right-scan's value from that day onward. 4. The best such combined sum, across every split point, is the maximum two-transaction profit.

Time: O(n) - two linear scans (left-to-right and right-to-left) plus one more linear pass to find the best split - still proportional only to the number of days. Space: O(n), for the two precomputed profit arrays.

n = 1 (no transaction is possible, profit 0); strictly decreasing prices (profit 0, since no transaction helps); and n = 10^5 (largest, confirming the two-pass left/right profit approach runs in O(n)).

This is a strong example of 'precompute both directions, then combine' - a reusable pattern for any problem asking about splitting an array into two independent halves and optimizing something across the split.