Maximum Profit with At Most Two Stock Transactions

You are given an array of integers where the i-th integer represents the price of a stock on day i. Your task is to find the maximum profit you can achieve by making 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 at the same time; you must sell the stock before you buy again.

The problem can be mathematically described as follows: Given an array \( P = [p_0, p_1, \ldots, p_{n-1}] \), compute \[ \text{maxProfit} = \max_{0 \leq i < n} \{ profit1[i] + profit2[i] \}, \] where profit1[i] is the maximum profit achievable in the range \([0, i]\) and profit2[i] is the maximum profit achievable in the range \([i, n-1]\).

If no profit is possible, output 0.

inputFormat

The input is given from stdin and consists of two lines:

• The first line contains a single integer \( n \) indicating the number of days.
• The second line contains \( n \) space-separated integers representing the stock prices for each day.

outputFormat

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

8
3 3 5 0 0 3 1 4

6