Stock Trading Profit Maximization

You are given an integer array prices where prices[i] represents the price of a given stock on day i. You are allowed to complete at most two transactions (i.e. buy and sell the stock at most twice). Note that you cannot hold more than one share at a time; you must sell the stock before you buy again.

Your task is to compute the maximum profit you can achieve. If no profit can be made, return 0.

Formally, if you denote the price on day i by prices[i], you are to maximize the total profit from at most two pairs of buy-sell operations. In mathematical notation, if the two transactions are represented as buying at day i and selling at day j with profit prices[j]-prices[i] (and similarly for the second transaction), then the transactions must satisfy j < k for the second transaction (if it exists). The allowed number of transactions is restricted by \(\leq 2\).

inputFormat

The input consists of two lines:

1. The first line contains a single integer n which represents the number of days.
2. The second line contains n space-separated integers where the i-th integer represents prices[i], the price of the stock on day i.

outputFormat

Output a single integer which is the maximum profit that can be achieved with at most two transactions. If no profit can be made, output 0.

8
3 3 5 0 0 3 1 4

6