1177. Best Time to Buy and Sell Stock III — At Most 2

Given daily stock prices, you may complete at most two transactions (no overlapping; sell before buying again). Return the maximum profit. The input is JSON {prices}.

Input: JSON {prices}.

Output: Integer — the maximum profit.

Examples

Input: {"prices":[3,3,5,0,0,3,1,4]}
Output: 6
Explanation: Two transactions profit 3 each.

Input: {"prices":[1,2,3,4,5]}
Output: 4
Explanation: One transaction is enough.

Input: {"prices":[1]}
Output: 0
Explanation: No transaction.

Constraints

• 1<=n<=10^5

Asked by