Best Time to Buy and Sell Stock II
Explanation & Solution
Description
Given an array prices where prices[i] is the price of a given stock on the ith day, find the maximum profit you can achieve.
You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). However, you must sell the stock before you buy again.
Note: You may not engage in multiple transactions simultaneously (you must sell before you buy again).
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 3. Total profit = 4 + 3 = 7.
Constraints
1 <= prices.length <= 3 × 10⁴0 <= prices[i] <= 10⁴
Approach
Greedy Techniques pattern
1. Initialize Profit Tracker
- Set
profit = 0to accumulate all gains - We will scan the array from left to right, looking at consecutive day pairs
2. Iterate Through Consecutive Days
- For each day
ifrom 1 toprices.length - 1, compute the differenceprices[i] - prices[i - 1] - This tells us how much the price changed from yesterday to today
3. Collect All Positive Differences
- If the difference is positive (price went up), add it to
profit - If the difference is zero or negative (price stayed flat or dropped), skip it
- This is equivalent to buying at every local valley and selling at every local peak
4. Return the Total Profit
- After scanning all consecutive pairs,
profitholds the maximum possible profit - Return
profit
Key Insight
The greedy approach works because any upward movement in price can be captured as profit. Summing all positive day-to-day differences is mathematically equivalent to buying at every valley and selling at every peak. For example, if prices go [1, 3, 5], the profit from buying at 1 and selling at 5 (profit = 4) equals (3-1) + (5-3) = 4. This runs in O(n) time and O(1) space, making a single pass through the array.
Visualization
Press ▶ or use ← → to step through