Best Time to Buy and Sell Stock II
Problem
Given an array prices where prices[i] is the price of a given stock on the ith day, return the maximum profit you can achieve by making as many transactions as you like (buy one and sell one share of the stock multiple times). You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
- 1 ≤ prices.length ≤ 3 * 10⁴
- 0 ≤ prices[i] ≤ 10⁴
Example
prices = [7,1,5,3,6,4]7Profit is generated only on days where price[i] exceeds price[i−1], because that increase is exactly the profit a single buy-then-sell action would realize under the unlimited-transactions rule. In the sequence 7→1→5→3→6→4, the price rises from 1→5 (profit 4) and from 3→6 (profit 3). Adding these gains gives the total profit of 7. Because unlimited transactions allow each positive daily increase to be realized immediately, every rise can be captured as its own buy-sell step. Any multi-day rise is simply the sum of its positive daily increases, so summing all positive differences always recovers the full achievable profit.
Approach
Straightforward Solution
A brute-force approach would try all possible pairs of buy and sell days, checking every combination to find the maximum profit. This approach is O(n^2) and inefficient for large inputs.
Core Observation
The maximum profit from multiple transactions can be decomposed into the sum of all positive price differences between consecutive days. This is because any sequence of buy-sell pairs that yields profit can be represented as the sum of these increments.
Path to Optimal
The key insight is that the problem can be simplified by recognizing that any profitable transaction can be broken down into smaller profitable steps. Instead of explicitly tracking buy and sell days, the algorithm accumulates profit whenever the price increases from one day to the next. This greedy approach avoids complex state tracking and reduces the problem to a single pass through the array.
Optimal Approach
Iterate through the prices array once, and whenever the price on day i is greater than on day i-1, add the difference to the total profit. This approach captures all profitable transactions implicitly and runs in O(n) time with O(1) space.
Time
O(n)
The algorithm makes a single pass through the prices array, performing constant-time operations per element.
Space
O(1)
Only a fixed number of variables are used to track the accumulated profit; no additional data structures scale with input size.
Pattern Spotlight
Greedy Algorithms (Incremental Profit Accumulation)
When allowed unlimited transactions, the maximum profit equals the sum of all positive price increments between consecutive days, as capturing every profitable step greedily yields the optimal total profit.
Solution
| 1 | class Solution:
|
| 2 | def maxProfit(self, prices: List[int]) -> int:
|
| 3 | profit = 0
|
| 4 |
|
| 5 | for i in range(1, len(prices)):
|
| 6 | if prices[i] > prices[i - 1]:
|
| 7 | profit += prices[i] - prices[i - 1]
|
| 8 |
|
| 9 | return profit |
Step-by-Step Solution
Accumulate Profit by Summing Positive Price Differences
| 3 | profit = 0
|
| 5 | for i in range(1, len(prices)):
|
| 6 | if prices[i] > prices[i - 1]:
|
| 7 | profit += prices[i] - prices[i - 1]
|
Objective
To iterate through the price array and add up all positive differences between consecutive days to calculate total profit.
Key Insight
By adding only the positive increments, the algorithm effectively simulates buying at every local minimum and selling at every local maximum without explicitly tracking these points. This greedy accumulation captures the total profit achievable through multiple transactions in a single pass.
Interview Quick-Check
Core Logic
The algorithm adds the difference prices[i] - prices[i-1] to profit only when this difference is positive, ensuring all profitable transactions are counted.
State & Boundaries
The loop starts from index 1 to compare each day with its previous day, ensuring no out-of-bounds access.
Common Pitfalls & Bugs
A common mistake is to try to track explicit buy and sell days, which complicates the solution unnecessarily.
Complexity
This approach runs in O(n) time and O(1) space, optimal for this problem.
Return the Total Accumulated Profit
| 9 | return profit |
Objective
To output the final computed maximum profit after processing all price differences.
Key Insight
Returning the accumulated profit variable completes the algorithm, providing the maximum achievable profit from unlimited transactions without violating the constraint of not holding multiple stocks simultaneously.
Interview Quick-Check
Core Logic
Returning the accumulated profit variable gives the final answer representing the sum of all profitable increments.
Line Analysis
This solution has 1 Critical line interviewers watch for.
profit += prices[i] - prices[i - 1]Add the positive price difference to the accumulated profit.
Adding only positive differences ensures the algorithm captures all profitable transactions without losing profit to price drops, effectively simulating multiple buy-sell pairs.
if prices[i] > prices[i - 1]:Check if the current day's price is higher than the previous day's price.
This condition identifies profitable opportunities where buying the previous day and selling today yields a positive gain.
profit = 0Initialize the profit accumulator to zero.
Starting with zero profit establishes a baseline for accumulating gains from profitable transactions; this variable holds the running total of all positive price differences.
return profitReturn the total accumulated profit after processing all days.
Returning the accumulated profit variable provides the final maximum profit achievable under the problem constraints.
for i in range(1, len(prices)):Iterate through the prices array starting from the second day.
Starting from index 1 allows comparison of each day's price with the previous day's price to identify profitable increments.
Test Your Understanding
Why does summing all positive differences between consecutive days yield the maximum profit when unlimited transactions are allowed?
Because every time the price is higher today than it was yesterday, the amount of that increase is exactly how much profit a buy-then-sell transaction would produce for that pair of days. Unlimited transactions mean you are allowed to take profit on every one of those increases. Adding all positive day-to-day increases therefore gives the total profit available across the entire price sequence, and no other strategy can produce more.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Best Time to Buy and Sell Stock II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Best Time to Buy and Sell Stock II drill