Best Time to Buy and Sell Stock III
You are given an array prices where prices[i] is the price of a given stock on the i^th day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously; you must sell the stock before you buy again.
Example 1
Input
prices = [3,3,5,0,0,3,1,4]Output
6Buy on day 4 at price 0 and sell on day 6 at price 3 for profit 3, then buy on day 7 at price 1 and sell on day 8 at price 4 for profit 3, totaling 6.
Example 2
Input
prices = [1,2,3,4,5]Output
4Buy on day 1 at price 1 and sell on day 5 at price 5 for profit 4; you cannot hold multiple transactions at the same time, so you must sell before buying again.
Constraints
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^5