All problems

Best Time to Buy and Sell Stock III

Hard · dynamic programming

The list prices holds the price of one share of a stock on each day, in order: prices[i] is the price on day i.

You may make at most two trades. A trade is one purchase of a single share followed by its sale on a later day. You can hold only one share at a time, so the second purchase must come on or after the day the first share is sold. Buying on the same day you sell is allowed.

Return the largest total profit you can make over both trades. If no trade makes money, return 0.

Examples

Example 1

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

Output: 11

Buy at 1 and sell at 5 for a profit of 4, then buy at 2 and sell at 9 for a profit of 7. The total is 11.

Example 2

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

Output: 4

One trade from 1 to 5 earns 4. Splitting it into two trades earns no more.

Example 3

Input: prices = [7, 5, 3, 1]

Output: 0

The price only falls, so the best choice is to make no trade.

Constraints