Best Time to Buy and Sell Stock II
Medium · Greedy · Array · Dynamic Programming · Greedy
Problem
prices[i] is the price of one share on day i. You may trade as many times as you like, but you can hold at most one share at a time: buy, then sell it before you buy again. Return the largest total profit you can make, or 0 if no trade helps.
Selling and buying again on the same day is allowed, so a long rise can be taken in one trade or as a chain of one-day trades — the profit is the same.
The one-trade version of this problem is Best Time to Buy and Sell Stock; here there is no limit on the number of trades, which changes the answer completely.
Examples
Input: prices = [7,1,5,3,6,4] Output: 7
Buy at 1 and sell at 5 for 4, then buy at 3 and sell at 6 for 3. One trade alone could make only 5.
Input: prices = [1,2,3,4,5] Output: 4
Buy on the first day and sell on the last. Selling and buying back every day earns the same 4.
Constraints
- 1 <= len(prices) <= 3 * 10^4
- 0 <= prices[i] <= 10^4
Approaches
- Try every buy and sell day — time O(n²), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
