Best Time to Buy and Sell Stock II
Last Updated: April 2, 2026
Understanding the Problem
In Problem Best Time to Buy and Sell Stock, you could only buy and sell once, so the goal was to find the single biggest gap between a low point and a later high point.
Here, you can make unlimited transactions (buy-sell pairs), but with one constraint: you can hold at most one share at a time. So you must sell before you buy again.
The key question becomes: how do we pick which days to buy and which to sell to maximize total profit?
If you look at a price chart, the answer is visually obvious: buy at every valley and sell at every peak. Every upward movement in price is profit you can capture. Every downward movement is a loss you can avoid by not holding the stock.
This observation leads us from a brute force exploration of all possibilities, through dynamic programming, to a surprisingly simple greedy solution.
Key Constraints:
1 <= prices.length <= 3 * 10^4→ With up to 30,000 elements, O(n^2) would give about 9 * 10^8 operations, which is borderline. O(n) or O(n log n) is safe. An exponential brute force (O(2^n)) is completely out of the question.0 <= prices[i] <= 10^4→ Non-negative prices, and the total profit across all transactions fits in a 32-bit integer (worst case: 30,000 days times 10,000 max price difference = 3 * 10^8).
Approach 1: Brute Force (Recursion)
Intuition
The most natural way to think about this problem: at every day, we have choices. If we don't hold a stock, we can either buy today or skip. If we hold a stock, we can either sell today or skip.
We can explore all possible combinations using recursion and return the maximum profit across all paths. This is exhaustive, so it's guaranteed to find the optimal answer.
Algorithm
- Define a recursive function that takes the current day index and whether we're currently holding a stock.
- Base case: if we've gone past the last day, return 0 (no more profit possible).
- If not holding a stock:
- Option A: Skip this day (recurse to next day, still not holding).
- Option B: Buy today (recurse to next day, now holding, subtract today's price).
- If holding a stock:
- Option A: Skip this day (recurse to next day, still holding).
- Option B: Sell today (recurse to next day, not holding, add today's price).
- Return the maximum of both options at each step.
Example Walkthrough
Code
- Time Complexity: O(2^n). At each day, we make 2 choices (buy/sell or skip), and there are n days. This creates a binary decision tree of depth n, giving us 2^n total paths to explore.
- Space Complexity: O(n). The recursion stack goes n levels deep (one level per day).
Many branches reach the same state. For example, solve(day=5, holding=false) gets called regardless of how we arrived there. There are only n * 2 unique states, so what if we memoized the result for each (day, holding) pair?
Approach 2: Dynamic Programming
Intuition
Notice something about the brute force: the result of solve(day, holding) only depends on two things: which day we're on and whether we currently hold a stock. There are only n * 2 unique states, but the brute force recomputes them over and over.
We can define two DP states:
notHolding[i]= maximum profit at the end of dayiwhen we do NOT hold a stock.holding[i]= maximum profit at the end of dayiwhen we DO hold a stock.
The transitions are:
notHolding[i] = max(notHolding[i-1], holding[i-1] + prices[i])- Either we already weren't holding (skip), or we sell today.holding[i] = max(holding[i-1], notHolding[i-1] - prices[i])- Either we were already holding (skip), or we buy today.
Since each day only depends on the previous day, we don't need arrays. Two variables are enough.
The DP captures every possible trading strategy in just two variables. At each day, we track the best possible outcome for both states (holding and not holding). By always taking the maximum of "keep current state" vs "transition," we guarantee the optimal sequence of buys and sells without explicitly enumerating them.
The key insight is that we use temporary variables (newNotHolding, newHolding) so that both updates use the previous day's values, not the current day's partially updated values.
Algorithm
- Initialize
notHolding = 0(start with no stock, zero profit) andholding = -prices[0](if we buy on day 0). - For each day from 1 to n-1:
- Calculate new
notHolding= max of (keep not holding) or (sell today). - Calculate new
holding= max of (keep holding) or (buy today). - Return
notHolding(we want to end without holding any stock for maximum profit).
Example Walkthrough
Code
- Time Complexity: O(n). We make a single pass through the prices array, doing O(1) work per day.
- Space Complexity: O(1). We only use a constant number of variables regardless of input size.
The DP is already O(n) time and O(1) space, but the logic isn't immediately obvious. Since there are no fees or cooldowns, is there a pattern in the price movements themselves that directly tells us the answer?
Approach 3: Greedy (Sum of Positive Differences)
Intuition
Here's the key insight that makes this problem beautifully simple. Consider what profit actually means for a multi-day hold:
If you buy on day 1 (price 1) and sell on day 3 (price 5), the profit is 5 - 1 = 4.
But notice: 5 - 1 = (2 - 1) + (3 - 2) + (5 - 3). Any multi-day profit can be decomposed into a sum of consecutive daily differences.
So instead of figuring out when to buy and sell, just collect every positive daily difference. If prices[i] > prices[i-1], that's profit you can capture. If prices[i] < prices[i-1], skip it (you wouldn't hold through a price drop).
This greedy strategy works because there are no transaction fees and no limit on the number of transactions. Every upward movement is free profit.
Algorithm
- Initialize
profit = 0. - For each day from 1 to n-1:
- If today's price is higher than yesterday's, add the difference to profit.
- Return profit.
Example Walkthrough
Code
- Time Complexity: O(n). Single pass through the array with O(1) work per element.
- Space Complexity: O(1). Only one variable (
profit) regardless of input size.