Maximum Profit with Two Stock Transactions

You are given a sequence of stock prices \(p_1, p_2, \ldots, p_n\) in chronological order. Your task is to determine the maximum profit achievable by performing at most two transactions.

A transaction consists of buying one stock and then later selling it. Note that you cannot engage in multiple overlapping transactions; you must sell a stock before you buy again. The profit from a single transaction is given by \(p_j - p_i\) where \(j > i\). The objective is to maximize the overall profit by possibly making two such transactions.

For example, given the prices [3, 3, 5, 0, 0, 3, 1, 4], the maximum profit is 6.

inputFormat

The input is provided via standard input. The first line contains an integer \(n\), the number of stock prices. The second line contains \(n\) space-separated integers \(p_1, p_2, \ldots, p_n\) representing the stock prices in chronological order. If \(n = 0\), the second line may be empty.

outputFormat

Output a single integer to standard output, representing the maximum profit achievable with at most two transactions.

8
3 3 5 0 0 3 1 4

6