Maximum Profit with Two Transactions

You are given an array of daily stock prices. Your task is to determine the maximum profit that can be achieved with at most two transactions. A transaction is defined as buying on one day and selling on a later day. Note that you cannot engage in multiple transactions simultaneously (i.e. you must sell the stock before you buy again).

The profit from one transaction is computed as follows:

$$Profit = price_{sell} - price_{buy}$$

Make sure that the two transactions do not overlap. If no profit can be made, output 0.

inputFormat

The first line of input contains an integer n representing the number of days. The second line contains n space-separated integers representing the stock prices for each day.

outputFormat

Output a single integer representing the maximum profit that can be achieved with at most two transactions.

8
3 3 5 0 0 3 1 4

6