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
PreviewThe key insight is that the problem can be simplified by recognizing that any profitable transaction can be broken down into smaller profitable steps…
Full step-by-step walkthrough on Pro →
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.
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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
To output the final computed maximum profit after processing all price differences.
1 more step with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 5 lines available on Pro.
Test Your Understanding
Why does summing all positive differences between consecutive days yield the maximum profit when unlimited transactions are allowed?
See the answer with Pro.
Related Problems
Greedy Algorithms 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