A jeweller trades in one gold coin. The list prices gives the price of the coin: prices[i] is the price on day i.
On each day she can buy the coin, sell it, do both (sell first, then buy again), or do nothing. She can own at most one coin at a time. She may trade as many times as she likes.
Return the largest total profit she can make over all the days.
Examples
Example 1:
Input: prices = [2,5,1,4,7]
Output: 9
Explanation: Buy at 2 and sell at 5 for a profit of 3. Buy again at 1 and sell at 7 for a profit of 6. The total is 9.
Example 2:
Input: prices = [1,2,3,4]
Output: 3
Explanation: Buy on the first day at 1 and sell on the last day at 4. The profit is 3.
Example 3:
Input: prices = [9,7,4,1]
Output: 0
Explanation: The price keeps falling, so she never buys and the profit is 0.