Maximum Profit with At Most Two Transactions

Given a list of stock prices for consecutive days, determine the maximum profit that can be achieved by performing at most two transactions. In each transaction, you buy one share and then sell it later. You cannot engage in multiple transactions simultaneously, meaning you must sell the stock before buying again.

The profit for a single transaction can be calculated using the formula: \(profit = price_{sell} - price_{buy}\). Your task is to choose the optimal days to buy and sell in order to maximize the total profit over at most two transactions.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(T\) representing the number of test cases. For each test case, the first line contains an integer \(N\), the number of days. The second line contains \(N\) space-separated integers which represent the stock prices on each day.

outputFormat

For each test case, output a single line to standard output (stdout) containing the maximum profit obtainable with at most two transactions.

2
8
3 3 5 0 0 3 1 4
5
1 2 3 4 5

6
4