Greedy Scan
What is this?
Imagine you could buy and sell a stock as often as you liked, with no fees, and you had tomorrow's prices in front of you. You would not think about which peak to hold for. You would simply capture every single rise. Whenever tomorrow is higher than today, buy today and sell tomorrow. Whenever it is lower, do nothing.
The insight worth carrying away is that a long climb and a chain of one-day trades earn exactly the same amount, so there is nothing to optimise.
Fun fact: buying at 1 and selling at 7 earns 6. Buying at 1, selling at 5, buying at 5 and selling at 7 also earns 6:
(5-1) + (7-5). The intermediate transactions telescope, which is why decomposing a rise into single-day trades costs nothing. That telescoping is the entire proof, and it is also why the problem changes character completely the moment a transaction fee or a limit on trades is introduced: then the intermediate trades do cost something, and it becomes dynamic programming.
🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.
Core idea: when the intermediate transactions are free, they telescope, so the maximum profit is simply the sum of every positive day-to-day difference, computed in one pass with no state at all.
1. The whole solution
def max_profit(prices):
return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))
There is no decision to make, no peak to find, no valley to remember. The reason is worth stating precisely in an interview: any profitable strategy can be decomposed into single-day gains, and every single-day gain is independently capturable. Since no falling step can ever contribute, taking all the rises is optimal.
Contrast with the single-transaction version, where you must track the minimum seen so far because you may only trade once. The moment the constraint is lifted, that state disappears entirely.
2. A 30-second worked example
Note the algorithm never identifies those two trades explicitly. It just adds +4 and +3 while skipping the falls. The trades are an interpretation of the sum, not something the code computes.
3. Where you'll actually meet this
- Interviews. The code is one line; the point is arguing why local gains summed equal the global optimum. It is the base case of the stock family.
- Total climb. "Total ascent" over an elevation profile is the sum of positive differences.
- Counters. The total a counter rose between samples, ignoring the drops, is the same sum.
4. Problems in this chapter
Best Time to Buy and Sell Stock II
Maximise profit with unlimited transactions. Sum every positive consecutive difference.
Pattern: sum of positive local gains. Target: O(n) time, O(1) space.
5. Common pitfalls
- Tracking a minimum price. That is the single-transaction problem. With unlimited trades it is unnecessary state.
- Hunting for peaks and valleys. It produces the same number with far more code and far more edge cases.
- Reaching for DP. Correct, and enormous overkill, but say that you know it becomes DP the moment fees or a transaction limit appear.
- Holding overnight across a fall. Since falls contribute nothing, there is never a reason to hold through one.
- Off-by-one on the loop. Start at index 1 and compare backwards, or you index past the end.
- Assuming at least two days. A single-day input must return 0, not crash.
6. Key takeaways
- Free intermediate transactions telescope, so a long rise and a chain of daily trades are worth the same.
- Sum the positive differences. That is the entire algorithm.
- No state is needed, which is precisely what "unlimited transactions" buys you.
- The single-transaction variant is a different problem, and needs the running minimum.
- Adding a fee or a trade limit turns this into DP. Knowing the boundary matters more than knowing the one-liner.
- Why interviewers like it: the one-line answer is easy to produce and easy to produce without understanding. The follow-up, "what changes if each trade costs £2?", is what they are actually asking.
Order: Best Time to Buy and Sell Stock II.
Best Time to Buy and Sell Stock II
Core idea: With unlimited trades and at most one share at a time, you don't need to find the perfect big swing. You can pocket every single up-day: buy at the close of any day that is cheaper than tomorrow, sell tomorrow. Sum every positive
prices[i] - prices[i-1]and you have the maximum possible profit, in one pass.
Problem, rephrased
You run a small trading bot on a single stock. You're given an array prices where prices[i] is the stock's price on day i, in chronological order. Unlike the single-transaction version, the bot may buy and sell as many times as it likes, but it can hold at most one share at any moment, so it must sell what it owns before buying again. (Selling and re-buying on the same day is allowed; it changes nothing.)
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson