Best Time to Buy and Sell Stock III

Hard

Given an array prices where prices[i] is the stock price on day i, return the maximum profit you can achieve with at most two transactions. You may not hold more than one share at a time (you must sell before you buy again).

Example 1

Input:  prices = [3,3,5,0,0,3,1,4]
Output: 6

Example 2

Input:  prices = [1,2,3,4,5]
Output: 4

Example 3

Input:  prices = [7,6,4,3,1]
Output: 0

Constraints

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^5