Leetcode - Best Time to Buy and Sell Stock II Solution

After solving the single transaction stock problem, I was curious about what would happen if I could make multiple transactions. This version turned out to have a surprisingly elegant solution. The key insight: if we can make multiple transactions, we should capture every single price increase.

If the price goes up from day 1 to day 2, and then up again from day 2 to day 3, we can buy on day 1, sell on day 2, then buy again on day 2 and sell on day 3. This is equivalent to buying on day 1 and selling on day 3. So we just need to sum up all the positive differences between consecutive days.

The Problem

This time, I'm given an array prices where prices[i] is the stock price on day i. I can buy and/or sell stock every day, and I can only hold one stock at a time. I can even buy and sell on the same day if I want.

The goal is to find the maximum profit from these transactions.

My Initial Confusion

At first, I thought this would be complicated. "Do I need to track when I buy and sell? What if I buy on day 1, sell on day 2, then buy again on day 3?" My mind was racing with all the possibilities.

Then I had an insight: if I can make multiple transactions, I should capture every single price increase. Why? Because if the price goes up from day 1 to day 2, and then up again from day 2 to day 3, I can:

• Buy on day 1, sell on day 2 (profit: price[2] - price[1])
• Buy on day 2, sell on day 3 (profit: price[3] - price[2])

This is the same as buying on day 1 and selling on day 3! So I just need to sum up all the positive differences between consecutive days.

The Solution

Here's what I came up with:

function maxProfit(prices) {
  let maxProfit = 0;

  // Check each day compared to the previous day
  for (let i = 1; i < prices.length; i++) {
    // If price increased, add that profit
    if (prices[i] > prices[i - 1]) {
      maxProfit += prices[i] - prices[i - 1];
    }
  }

  return maxProfit;
}

// Example usage:
const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // Output: 7

Let me trace through the example:

• Day 0 to Day 1: 7 → 1 (decrease, no profit)
• Day 1 to Day 2: 1 → 5 (increase! profit = 4)
• Day 2 to Day 3: 5 → 3 (decrease, no profit)
• Day 3 to Day 4: 3 → 6 (increase! profit = 3)
• Day 4 to Day 5: 6 → 4 (decrease, no profit)

Total profit: 4 + 3 = 7. Perfect!

Why This Works

The key insight is that we want to capture every price increase. It doesn't matter if prices go up and down multiple times. We just need to buy before each increase and sell after. Since we can buy and sell on the same day, we can effectively "buy" at the start of each increase and "sell" at the end.

Java Version

public class StockProfit {
    public static int maxProfit(int[] prices) {
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }

        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(prices)); // Output: 7
    }
}

What Surprised Me

I was surprised by how simple the solution was. I initially thought I'd need dynamic programming or some complex state tracking, but the greedy approach works perfectly here. The algorithm is O(n) time and O(1) space. Can't get much better than that!

Key Takeaways

• Sometimes the simplest approach is the best approach
• Greedy algorithms work when you can make locally optimal choices (capture every increase)
• Don't overthink problems. The solution might be simpler than you expect.
• This pattern of "capture all increases" appears in other problems too

This problem was a great reminder that elegant solutions often come from understanding the problem deeply rather than applying complex techniques. I hope this helps you in your coding journey!