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.

The one-line 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

prices:      7   1   5   3   6   4
differences:   -6  +4  -2  +3  -2
positive:           4       3
                                total profit = 7

as trades:  buy 1 → sell 5  (+4)
            buy 3 → sell 6  (+3)

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

• Trading and rebalancing. Zero-fee strategies capture every favourable move; this is the theoretical upper bound against which fee-bearing strategies are measured.
• Resource top-ups. Any scenario where you can freely take and release a resource captures each favourable swing independently.
• Energy arbitrage. Charge and discharge a battery on every price rise when cycling costs are negligible.
• Elevation and effort totals. "Total climb" on a route is exactly the sum of positive differences, and fitness trackers compute it this way.
• Signal analysis. Total variation of a series decomposes into positive and negative parts identically.

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

1. Free intermediate transactions telescope, so a long rise and a chain of daily trades are worth the same.
2. Sum the positive differences. That is the entire algorithm.
3. No state is needed — which is precisely what "unlimited transactions" buys you.
4. The single-transaction variant is a different problem, and needs the running minimum.
5. Adding a fee or a trade limit turns this into DP. Knowing the boundary matters more than knowing the one-liner.
6. 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.