#122
Best Time to Buy and Sell Stock II
Medium Collect every rise
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
You may buy and sell a stock many times (holding at most one share at a time). Return the maximum total profit.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: many trades allowed; maximise profit.
Why this works: any profitable run equals the sum of its daily rises, so collect every rise.
Example: [7, 1, 5, 3, 6, 4]
rises: 1→5 (+4), 3→6 (+3)total 7
✦Hints open one at a time
Any profit over several days equals the sum of the daily increases in between.
So take every day-to-day increase.
↗Approach
Add max(0, prices[i] − prices[i − 1]) for each i. This equals buying at every local low and selling at every local high.
</>Solution (Java)
class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1]; // take every rise
}
return profit;
}
}!Common mistake
Looking for the single best buy/sell pair — that's the one-transaction problem.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Greedy
🎬 Episodes 69–73: video coming soon