A vendor trades a single share. The list prices gives its price: prices[i] is the price on day i. She may make as many trades as she likes, but she must follow two rules:
- She can own only one share at a time, so she sells before she buys again.
- The day after a sale is a rest day. She cannot buy on that day.
Return the largest total profit she can make.
Examples
Example 1:
Input: prices = [4,7,3,2,9]
Output: 10
Explanation: Buy at 4 and sell at 7 for a profit of 3. Rest on the day the price is 3. Buy at 2 and sell at 9 for a profit of 7. The total is 10.
Example 2:
Input: prices = [3]
Output: 0
Explanation: With only one day, she cannot buy and sell, so the profit is 0.
Example 3:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on the first day at 1 and sell on the last day at 5. The profit is 4, which is the best.