Course contentsShow
← Computer Science
Lesson 902 of 2,87221. Greedy AlgorithmsFree lesson

Buy Maximum Stocks with K Transactions

Maximize profit by greedily buying and selling stocks whenever price increases on consecutive days.

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 3to3 to 5 to 7,youshouldbuyat7, you should buy at 3 and sell at 7(profit=7 (profit = 4). But here's the greedy trick: that's mathematically identical to buying at 3,sellingat3, selling at 5 (+2),thenbuyingat2), then buying at 5 and selling at 7(+7 (+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.