You are given prices, where prices[i] is a stock's price on day i. You may buy and sell as many times as you like, but you can hold at most one share at a time (you may sell and buy again on the same day). Return the maximum total profit.
- 1 <= prices.length <= 3 * 10^4
- 0 <= prices[i] <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries every set of buy and sell days, which is exponential. Since there is no limit on transactions and no fee, every upward step of the price chart can be collected. A long climb from day a to day b gives prices[b] - prices[a], which is exactly the sum of the daily increases along the way. So the greedy rule "take every positive daily difference" is safe: it collects every rise and never pays for a fall, and no strategy can earn more than the total of all rises.
Algorithm
- Set
profit = 0. - For each day
ifrom 1: ifprices[i] > prices[i-1], add the difference toprofit. - Return
profit.
O(n)Space: O(1)class Solution: def maxProfit(self, prices: List[int]) -> int: profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i - 1]: profit += prices[i] - prices[i - 1] # collect every rise return profit