Best Time to Sell Stock II [Greedy]

Greedy Algorithm Medium

Python Java C++

def maxProfit(prices):
    profit = 0
    
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
            
    return profit

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]; 
                
        return profit;
    }
}

class Solution {
public:
    int maxProfit(vector& prices) {
        int profit = 0;
        
        for (int i = 1; i < prices.size(); i++)
            if (prices[i] > prices[i - 1])
                profit += prices[i] - prices[i - 1];
                
        return profit;
    }
};

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith day. Design an algorithm to find the maximum profit by buying and selling the stock multiple times. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions: you must sell the stock before you buy again.

Detailed Explanation

Approach

The solution uses a greedy approach by capturing every possible profit opportunity. If the price tomorrow is higher than today, we buy today and sell tomorrow. This approach works because we can break down any profitable sequence into a series of daily profits.

Key Concepts

1. Valley-Peak Approach: Buy at every valley and sell at every peak
2. Daily Profits: Capture every positive price difference between consecutive days
3. Multiple Transactions: Can buy immediately after selling

Algorithm Steps

1. Initialize total profit as 0
2. Iterate through prices starting from index 1:
   • If current price is higher than previous price
   • Add the difference to total profit
3. Return total accumulated profit

Visual Example

Input: prices = [7,1,5,3,6,4] Step by step: 7 → 1: No profit (price decreased) 1 → 5: +4 profit (buy at 1, sell at 5) 5 → 3: No profit (price decreased) 3 → 6: +3 profit (buy at 3, sell at 6) 6 → 4: No profit (price decreased) Total profit = 7 (4 + 3) Transactions: 1. Buy at 1, sell at 5: +4 2. Buy at 3, sell at 6: +3

Time and Space Complexity

• Time Complexity: O(n) - Single pass through the array
• Space Complexity: O(1) - Only using one variable

Why This Works

This approach works because any profitable sequence can be broken down into a series of profitable one-day transactions. For example, if we can profit by buying on day 1 and selling on day 4, this is equivalent to buying on day 1, selling on day 2, buying on day 2, selling on day 3, and so on up to day 4 (if each consecutive day has a higher price).

Edge Cases

• Array length ≤ 1: Return 0
• Prices always decreasing: Return 0
• All prices same: Return 0
• Single valley-peak: Return their difference

Common Mistakes

• Trying to track actual buy/sell days
• Over-complicating with valley-peak tracking
• Not realizing you can sell and buy on the same day
• Missing the fact that capturing all positive differences is optimal