Buy Maximum Stocks with K Transactions
What you'll learn: How to maximize profit by greedily buying and selling stocks whenever the price increases between consecutive days.
The Core Idea
Imagine you're at a market where you can see tomorrow's prices today. When should you buy and sell to maximize profit? The greedy insight is simple: buy before every price increase and sell right after.
If the stock price goes from 5 to 3 and sell at 4). But here's the greedy trick: that's mathematically identical to buying at 5 (+5 and selling at 2). Both give you $4 total.
This means whenever prices[i+1] > prices[i], you should "capture" that increase by adding prices[i+1] - prices[i] to your profit. You're essentially executing a transaction across every consecutive upward move.
How It Works
Given an array of prices [7, 1, 5, 3, 6, 4]:
- Day 0→1: price drops (7→1), skip
- Day 1→2: price rises (1→5), profit += 4
- Day 2→3: price drops (5→3), skip
- Day 3→4: price rises (3→6), profit += 3
- Day 4→5: price drops (6→4), skip
Total profit = 7 (you captured every upward swing)
This greedy approach works because you can make unlimited transactions with no cooldown. By buying before every rise and selling immediately after, you never miss an opportunity.
Why It's Greedy
The algorithm makes the greedy choice at each step: if tomorrow's price is higher than today's, capture that profit immediately. No need to look further ahead or reconsider past decisions—each local gain contributes to the global optimum.
Key Takeaway: When unlimited stock transactions are allowed, maximize profit by greedily summing every consecutive price increase—buy low, sell high at every opportunity.