Best Time to Buy and Sell Stock II
Medium · greedy
You know the price of a share on each of the next days: prices[i] is the price on day i.
You may trade as often as you like, but you can hold at most one share at a time. On any day you may sell the share you hold, buy one share, or sell first and then buy again, always at that day's price. You can also choose to do nothing.
Return the largest total profit you can make. If no trade makes money, return 0.
Examples
Example 1
Input: prices = [3, 1, 4, 2, 6]
Output: 7
Buy at 1 and sell at 4 for 3, then buy at 2 and sell at 6 for 4. The total is 7.
Example 2
Input: prices = [9, 7, 5, 4]
Output: 0
Prices only fall, so it is best not to trade.
Example 3
Input: prices = [2, 5]
Output: 3
Constraints
- 1 <= len(prices) <= 3 * 10^4
- 0 <= prices[i] <= 10^4