Maximum Profit with Two Stock Transactions

Given a list of daily stock prices, determine the maximum profit that can be achieved by performing at most two transactions. A transaction consists of buying and then later selling a single share of the stock. Note that you must sell the stock before you can buy again (i.e., no overlapping transactions are allowed).

The problem requires an efficient algorithm to account for the possibility of zero, one, or two profitable transactions. The solution should use dynamic programming techniques to track the maximum profit at each transaction stage.

Mathematical Formulation:

Let \(price[i]\) be the price on day \(i\). Define:

• \(first\_buy = \max(-price[i])\)
• \(first\_sell = \max(first\_buy + price[i])\)
• \(second\_buy = \max(first\_sell - price[i])\)
• \(second\_sell = \max(second\_buy + price[i])\)

The answer is given by \(second\_sell\), representing the maximum profit after completing up to two transactions.

inputFormat

The input is given via standard input (stdin) in the following format:

 n
 price_1 price_2 ... price_n

Where:

• n: an integer indicating the number of days (if n is 0, the list is empty).
• price_i: the stock price on day i.

outputFormat

The output should be printed to standard output (stdout) as a single integer representing the maximum profit that can be achieved by performing at most two transactions.

## sample

8
3 3 5 0 0 3 1 4

6