Best Time to Buy and Sell Stock III
Return the maximum profit with at most two transactions.
Examples
Input: [3,3,5,0,0,3,1,4]
Output: 6
Input: [1,2,3,4,5]
Output: 4
Hints
Use dynamic programming with four variables to track the maximum profit after each buy and sell operation (buy1, sell1, buy2, sell2).
Initialize buy1 and buy2 to negative infinity (or a very small number) and sell1 and sell2 to 0, then iterate through the prices array to update these variables.
For each price, update the variables in the following order: buy1 = max(buy1, -price), sell1 = max(sell1, buy1 + price), buy2 = max(buy2, sell1 - price), sell2 = max(sell2, buy2 + price). The final answer will be sell2.
Related Problems
Best Time to Buy and Sell Stock III
Return the maximum profit with at most two transactions.