122. Best Time to Buy and Sell Stock II
You are given an array prices where prices[i] is the price of a single share on day i.
This time there is no limit on the number of trades: on any day you may buy the share or sell the one you are holding, and you may even sell and re-buy on the same day. The only rule is that you can hold at most one share at a time — you must sell before buying again.
Return the largest total profit you can collect across all your trades. If the market never rises, make no trades and return 0.
Example 1:
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 7
Explanation: Two trades do it: buy at 1 and sell at 5 (profit 4), then buy at 3 and sell at 6 (profit 3), for a total of 7. No schedule beats that.
Example 2:
Input: prices = [1, 2, 3, 4, 5]
Output: 4
Explanation: In a steadily rising market you can simply buy on day 0 and sell on day 4 for 5 - 1 = 4. Selling and re-buying along the way earns exactly the same total.
Constraints:
- 1 ≤ prices.length ≤ 10⁵
- 0 ≤ prices[i] ≤ 10⁴
Hints:
Because you can trade as often as you like, any long climb can be broken into one-day steps: holding from day i to day j earns the same as pocketing every daily change along the way.
So a rise from one day to the next is always worth taking. What happens to the total if you simply add up every positive prices[i+1] - prices[i]?
If greedy feels hand-wavy, model it as a state machine: each day you are either holding a share or holding cash, and each state's best value depends only on yesterday's two states.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: prices = [7, 1, 5, 3, 6, 4]
Expected output: 7