Best Time to Buy and Sell Stock II

How it works

The key insight is that we can capture every upward price movement. If the price goes up from day i to day i+1, we can always "buy" on day i and "sell" on day i+1 to capture that profit. We do not need to track actual transactions because consecutive gains are equivalent to holding through multiple days. For example, buying at 1, holding through 3, 5, and selling at 6 gives the same profit as buying at 1, selling at 3, buying at 3, selling at 5, buying at 5, and selling at 6.

Steps

1. Initialize a profit variable to 0.
2. Iterate through the prices from day 1 to the last day.
3. If today's price is higher than yesterday's price, add the difference to profit.
4. Return the total profit.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Confusing with Best Time to Buy and Sell Stock I

This problem allows unlimited transactions, while Stock I only allows one. Using the Stock I approach (tracking min price and max difference) will undercount the total profit.

Missing Consecutive Gains

The greedy approach works because consecutive daily gains are equivalent to one larger transaction. Buying at 1, selling at 5 equals buying at 1, selling at 3, buying at 3, selling at 5. Missing this insight leads to overcomplicating the solution.

Adding Negative Profits

When using the greedy approach, only add the difference when prices[i] > prices[i-1]. Adding negative differences (price drops) reduces your profit incorrectly.

Off-by-One in Loop

When comparing consecutive days, start the loop at index 1 (not 0) to safely access prices[i-1]. Starting at 0 causes an index out of bounds error.

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        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(vector<int>& 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;
    }
};