In the single-transaction version of this problem, the goal is to find the one biggest gap between a low price and a later high price. This version removes the limit: you can make as many buy-sell transactions as you want, with one constraint. You can hold at most one share at a time, so you must sell before you buy again.

The problem reduces to picking which days to buy and which to sell so that total profit is maximized. On a price chart, the best strategy is to buy at every valley and sell at every peak. Every upward movement is profit you can capture, and every downward movement is a loss you avoid by not holding.

The approaches below build up to that idea: a brute force over all buy/sell decisions, a two-state dynamic program, and two O(n) solutions that read the profit directly off the price movements.

Key Constraints:

Intuition

Each day offers two choices that depend on the current state. Without a share in hand, we can buy today or skip. With a share in hand, we can sell today or skip.

Recursion can explore every combination of these decisions and return the maximum profit across all paths. Because it tries every legal sequence of trades, it is guaranteed to find the optimal answer.

Algorithm

Example Walkthrough

Code

Many branches reach the same state. solve(day=5, holding=false) returns the same value no matter which trades came before it, yet the recursion recomputes it once per path. There are only n * 2 distinct (day, holding) states, and computing each one once collapses the exponential tree into linear work.

Intuition

The result of solve(day, holding) depends only on the day index and whether we hold a share, so two values per day summarize every possible trading history up to that point.

We can define two DP states:

The transitions are:

Since each day only depends on the previous day, we don't need arrays. Two variables are enough.

Algorithm

Example Walkthrough

Code

The DP already runs in O(n) time and O(1) space, so the remaining improvements are conceptual rather than asymptotic. With no fees, cooldowns, or transaction limits, the optimal buy and sell days can be read directly off the shape of the price curve, which is what the next two approaches do.

Intuition

The chart picture from the introduction translates directly into code: buy at the bottom of every drop (a valley) and sell at the top of the rise that follows (a peak). A single pointer can find these pairs in order. From the current position, walk forward while the price keeps falling to find the next valley, then walk forward while the price keeps rising to find the peak after it. Each valley-to-peak climb is one transaction, and its profit is peak minus valley.

Beyond the profit total, this scan recovers the actual buy and sell days, and it uses the fewest transactions that still achieve the maximum profit, since each maximal climb is captured in a single trade.

Algorithm

The >= and <= comparisons handle plateaus: equal prices are skipped during the descent and walked through during the climb. If prices end on a decline, the final valley is the last day, the peak equals the valley, and that pair adds nothing.

Example Walkthrough

Code

The peak-valley scan still tracks where each transaction starts and ends. If only the total profit matters, that bookkeeping can be dropped entirely.

Intuition

A multi-day hold decomposes into consecutive daily differences. With prices 1, 2, 3, 5 over four days, buying at 1 and selling at 5 earns 5 - 1 = 4, and that same profit telescopes into (2 - 1) + (3 - 2) + (5 - 3). Every transaction's profit, no matter how long the hold, is a sum of one-day differences.

So no transaction structure is needed at all. If prices[i] > prices[i - 1], that difference is profit captured by holding from day i - 1 to day i. If the price drops, don't hold through the drop. Summing every positive consecutive difference gives the answer.

This sum is optimal for two reasons. It is an upper bound: any transaction's profit telescopes into the daily differences inside its span, which is at most the sum of the positive ones, and transactions never overlap, so no difference is counted twice. It is also achievable: holding across exactly the rising days is a legal strategy because transactions are unlimited and fee-free. The total matches what the peak-valley scan computes, accumulated one day at a time instead of one climb at a time.

Algorithm

Example Walkthrough

Code