The statement allows as many transactions as we like while never holding two shares. That freedom has a surprisingly local consequence: every rise between two consecutive days can be collected on its own. A trade that buys on day a and sells on day b earns prices[b] - prices[a], which is exactly the telescoping sum of the one-day differences prices[a+1] - prices[a], prices[a+2] - prices[a+1], and so on up to prices[b] - prices[b-1]. Splitting the trade into a buy-sell on each of those days therefore earns the same money, and the no-overlap constraint is respected because each pair is flat again by the end of its day. The maximum profit is thus the sum of all positive adjacent differences — the rises — because a falling difference contributes a negative amount that no optimal strategy would ever take.
Brute Force: Explore Every Decision
Time O(2^n)Space O(n)The most direct reading of the rules is a recursion over days with a single boolean for whether a share is held. On each day there are two choices: do nothing, or act. When flat, acting means buying (pay the price, start holding); when holding, acting means selling (receive the price, go flat). The answer is the best of all branches starting flat on day 0.
class Solution: def maxProfit(self, prices: list[int]) -> int: n = len(prices)
def best(day: int, holding: bool) -> int: if day == n: return 0 # Option 1: do nothing today and move on. outcome = best(day + 1, holding) if holding: # Option 2: sell today and become flat. outcome = max(outcome, prices[day] + best(day + 1, False)) else: # Option 2: buy today and start holding. outcome = max(outcome, -prices[day] + best(day + 1, True)) return outcome
return best(0, False)Why it is exponential: every day spawns two branches, so the recursion tree has about 2^n leaves and the work is O(2^n) time. The only space cost is the recursion stack, which is O(n) deep. It is correct but hopeless for prices.length up to 3 * 10^4, and the branches overlap massively — the same (day, holding) state is recomputed from many paths.
Dynamic Programming: Holding or Flat
Time O(n)Space O(1)The brute force recomputes the same states, so name them. Let hold be the best profit achievable through today while holding a share, and cash the best profit while flat. Each day there are exactly two transitions per state: keep the current status, or flip it at today’s price. Buying subtracts price from the flat profit; selling adds price to the holding profit. Only the previous day’s two values are ever needed, so two variables replace the whole table.
class Solution: def maxProfit(self, prices: list[int]) -> int: # hold: best profit while holding a share; cash: best profit while flat. hold = -prices[0] cash = 0 for price in prices[1:]: prev_hold = hold hold = max(hold, cash - price) cash = max(cash, prev_hold + price) return cashWhy it is optimal: the state (day, holding) captures everything the future needs — the day is encoded in the loop position and holding is explicit — so the recurrence is a correct dynamic program. Each day does constant work, giving O(n) time, and only two numbers are live at a time, giving O(1) space. prev_hold is cached so that a buy and a sell never happen on the same simulated day, though even that would net zero. This state machine is the version that extends to a transaction limit or a cooldown.
Greedy: Sum the Rises
OptimalTime O(n)Space O(1)Since a multi-day trade is worth exactly the daily rises it spans, the only question is which rises to keep. Every positive difference is free money and never blocks another trade — after harvesting a rise we are flat again — while a negative difference only appears inside a losing trade. So scan the array once and add prices[i] - prices[i - 1] whenever it is positive, ignoring the rest.
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] return profitWatch the scan compare each day with the day before it and fold every rise into the running total. The panels stay fixed; only the highlighted days and the numbers move.
Prices
Adjacent pair
Running profit
each day is compared with the day before it; only positive differences are added
Unlimited trades, at most one share held. Every single-day rise can be banked on its own, so the scan sums the rises and ignores the drops. Profit starts at 0.
Why it is optimal: one pass with a single accumulator, so O(n) time and O(1) extra space. Correctness follows from the telescoping argument: any feasible strategy is a set of disjoint intervals, and each interval’s profit equals the sum of the positive and negative daily differences inside it. Dropping every negative term can only increase the total, and the remaining sum of positive terms is achievable by trading each rise independently — so this sum is both an upper bound and attainable.