Maximum Profit with At Most Two Transactions

You are given a sequence of daily stock prices. Your task is to compute the maximum profit from at most two transactions. A transaction is defined as buying and then later selling one share of the stock. Note that you must sell the stock before you buy it again.

The profit of a single transaction is given by the formula: \(\text{Profit} = \text{selling price} - \text{buying price}\). You are allowed to complete at most two such transactions. If no profit can be made, output 0.

Example:

• For prices = [3,3,5,0,0,3,1,4], the maximum profit is 6.
• For prices = [1,2,3,4,5], the maximum profit is 4.
• For prices = [7,6,4,3,1], the maximum profit is 0.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(n\) representing the number of stock prices. The second line contains \(n\) space-separated integers representing the stock prices.

If \(n = 0\), it means the list of stock prices is empty.

outputFormat

Output a single integer to standard output (stdout) representing the maximum profit achieved with at most two transactions.

8
3 3 5 0 0 3 1 4

6