Problem Description

You have an array prices where prices[i] represents the stock price on day i.

You can perform multiple transactions (buy and sell) with these rules:

• You can buy and/or sell the stock on any day
• You can only hold at most one share at a time (must sell before buying again)
• You can buy and sell on the same day

Your goal is to find the maximum total profit you can achieve by making as many transactions as you want.

For example, if prices are [1, 3, 2, 5]:

• Buy on day 0 at price 1, sell on day 1 at price 3: profit = 2
• Buy on day 2 at price 2, sell on day 3 at price 5: profit = 3
• Total maximum profit = 2 + 3 = 5

The solution uses a greedy approach: whenever the price increases from one day to the next, we capture that profit by buying on the previous day and selling on the current day. The code sum(max(0, b - a) for a, b in pairwise(prices)) calculates the sum of all positive price differences between consecutive days, which gives us the maximum possible profit.

Intuition

The key insight is that since we can make as many transactions as we want, we should capture every possible profit opportunity.

Think about it this way: if you could see the future stock prices, when would you trade? You'd want to buy right before every price increase and sell right before every price decrease.

Looking at a price graph, imagine it as a series of peaks and valleys. The maximum profit comes from buying at every valley and selling at every peak. But here's the clever part - this is equivalent to capturing all the upward movements in the price.

For example, if prices go from 1 → 3 → 2 → 5:

• From day 0 to 1: price increases by 2 (we profit)
• From day 1 to 2: price decreases by 1 (we don't trade)
• From day 2 to 3: price increases by 3 (we profit)

Notice that we only care about positive differences between consecutive days. Any time prices[i+1] > prices[i], we can profit by buying on day i and selling on day i+1.

This leads to the elegant solution: sum all positive differences between consecutive days. Even if there's a multi-day upward trend like 1 → 2 → 3 → 4, capturing each daily gain (1→2, 2→3, 3→4) gives the same total profit as holding from 1→4. This is why sum(max(0, b - a) for a, b in pairwise(prices)) works - it adds up all the profitable daily movements while ignoring the losses.

Solution Approach

The solution implements a greedy algorithm that captures profit from every price increase between consecutive days.

Implementation Details:

1. Iterate through consecutive price pairs: Using pairwise(prices), we get pairs of consecutive prices (a, b) where a is the price on day i and b is the price on day i+1.

2. Calculate daily profit: For each pair, we compute b - a:

   • If b - a > 0: The price increased, so we make a profit by buying at price a and selling at price b
   • If b - a ≤ 0: The price decreased or stayed the same, so we don't trade (profit = 0)

3. Use max(0, b - a): This ensures we only count positive differences (profits) and ignore negative differences (losses).

4. Sum all profits: The sum() function adds up all the individual daily profits to get the maximum total profit.

Why this works:

The greedy approach is optimal because:

• We're not limited in the number of transactions
• We can't hold multiple stocks simultaneously
• Any profitable sequence can be decomposed into individual daily gains

For example, if prices are [1, 2, 3, 4]:

• Instead of one transaction (buy at 1, sell at 4) with profit = 3
• We can do three transactions: (1→2) + (2→3) + (3→4) = 1 + 1 + 1 = 3
• Both give the same total profit!

The time complexity is O(n) where n is the length of the prices array, and space complexity is O(1) as we only track the running sum.

Example Walkthrough

Let's walk through the solution with prices = [7, 1, 5, 3, 6, 4].

Step 1: Identify consecutive price pairs Using pairwise(prices), we get:

• Pair 1: (7, 1) → day 0 to day 1
• Pair 2: (1, 5) → day 1 to day 2
• Pair 3: (5, 3) → day 2 to day 3
• Pair 4: (3, 6) → day 3 to day 4
• Pair 5: (6, 4) → day 4 to day 5

Step 2: Calculate profit for each pair For each pair (a, b), we compute max(0, b - a):

• Pair 1: max(0, 1 - 7) = max(0, -6) = 0 (price dropped, don't trade)
• Pair 2: max(0, 5 - 1) = max(0, 4) = 4 (price rose, buy at 1, sell at 5)
• Pair 3: max(0, 3 - 5) = max(0, -2) = 0 (price dropped, don't trade)
• Pair 4: max(0, 6 - 3) = max(0, 3) = 3 (price rose, buy at 3, sell at 6)
• Pair 5: max(0, 4 - 6) = max(0, -2) = 0 (price dropped, don't trade)

Step 3: Sum all profits Total profit = 0 + 4 + 0 + 3 + 0 = 7

Verification: Our algorithm effectively executed these transactions:

• Buy on day 1 at price 1, sell on day 2 at price 5: profit = 4
• Buy on day 3 at price 3, sell on day 4 at price 6: profit = 3
• Total profit = 4 + 3 = 7

This greedy approach captured every upward price movement while avoiding all downward movements, achieving the maximum possible profit.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the prices array. This is because the pairwise function iterates through the array once to create consecutive pairs, and the sum function with the generator expression processes each pair exactly once. The total number of pairs generated is n-1, resulting in linear time complexity.

The space complexity is O(1). While pairwise creates an iterator that generates pairs on-the-fly, it doesn't store all pairs in memory simultaneously. The generator expression max(0, b - a) for a, b in pairwise(prices) also computes values one at a time without storing them. Only a constant amount of extra space is used for variables like the running sum and the current pair being processed.

Common Pitfalls

1. Misunderstanding the Greedy Strategy as "Cheating"

Pitfall: Many people initially think the greedy approach is incorrect because it seems like we're "looking into the future" by buying and selling on consecutive days whenever there's a profit. They might think: "How can I know tomorrow's price when deciding to buy today?"

Why it's not a problem: The algorithm doesn't actually require future knowledge. We're analyzing historical data to find the maximum profit that could have been achieved. The consecutive day trading is mathematically equivalent to holding through multiple profitable days.

Example:

• Prices: [1, 2, 3, 4]
• Greedy: Buy at 1, sell at 2 (+1), buy at 2, sell at 3 (+1), buy at 3, sell at 4 (+1) = 3 profit
• Alternative: Buy at 1, sell at 4 = 3 profit
• Both strategies yield the same result!

2. Trying to Track Buy/Sell States Explicitly

Pitfall: Overcomplicating the solution by maintaining boolean flags or state variables to track whether we currently own stock:

# Overcomplicated approach
holding_stock = False
buy_price = 0
total_profit = 0

for i in range(len(prices)):
    if not holding_stock and i < len(prices) - 1 and prices[i] < prices[i + 1]:
        buy_price = prices[i]
        holding_stock = True
    elif holding_stock and (i == len(prices) - 1 or prices[i] > prices[i + 1]):
        total_profit += prices[i] - buy_price
        holding_stock = False

Solution: The greedy approach eliminates the need for state tracking. Simply sum all positive differences between consecutive days.

3. Edge Case: Single Element or Empty Array

Pitfall: Not handling arrays with fewer than 2 elements properly, which could cause index out of bounds errors.

Solution: The provided solution naturally handles this since range(1, len(prices)) produces an empty range when len(prices) < 2, resulting in a total profit of 0 (which is correct).

4. Integer Overflow in Other Languages

Pitfall: In languages with fixed-size integers (like Java or C++), summing many large profits could cause overflow.

Solution: In Python, integers have arbitrary precision so this isn't an issue. In other languages, use appropriate data types (e.g., long long in C++ or long in Java) or check for overflow conditions.

5. Misunderstanding When to Buy and Sell

Pitfall: Thinking you need to find explicit "valleys" (local minima) and "peaks" (local maxima) for buy/sell points:

# Unnecessarily complex peak-valley approach
i = 0
valley = peak = prices[0]
max_profit = 0

while i < len(prices) - 1:
    while i < len(prices) - 1 and prices[i] >= prices[i + 1]:
        i += 1
    valley = prices[i]
    while i < len(prices) - 1 and prices[i] <= prices[i + 1]:
        i += 1
    peak = prices[i]
    max_profit += peak - valley

Solution: The greedy approach is simpler and equivalent - just capture every upward price movement, regardless of whether it's part of a larger trend or not.