You are given a list of integers prices where prices[i] is the price of a stock on day i, in chronological order.
You may complete at most two transactions. Each transaction is one buy followed later by one sell, and you can hold at most one share at a time, so you must sell before you can buy again. Note that you are not required to trade at all, and the answer is 0 when no profitable trade exists.
Return the maximum total profit you can make.
Examples
Example 1
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 3 (price 0) and sell on day 5 (price 3) for a profit of 3. Buy on day 6 (price 1) and sell on day 7 (price 4) for a profit of 3. Total profit is 3 + 3 = 6.
Example 2
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: One transaction, buying on day 0 and selling on day 4, already captures the entire rise. A second transaction cannot add anything more.
Example 3
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: The price only falls, so no transaction is ever profitable.
Constraints
0≤n≤105 where n=prices.length
0≤prices[i]≤104
Loading editor...
Run checks the sample cases; Submit runs every case.
Samples 3
Custom 0
passedwrong answertime limiterrorran, no expected valuenot run