112. Best Time to Buy and Sell Stock III

You may complete at most two transactions (buy then sell). You may not hold multiple stocks simultaneously. Return the maximum profit.

Input: Integer array prices where prices[i] is stock price on day i.

Output: Integer — maximum profit with at most 2 transactions.

Examples

Example 1

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy at 0 sell at 3 (profit 3), buy at 1 sell at 4 (profit 3). Total 6.

Example 2

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy once at 1, sell at 5. One transaction suffices.

Example 3

Input: [7,6,4,3,1]
Output: 0
Explanation: No profitable transaction possible.