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. The extra freedom changes the calculation: every rise from one day to the next can contribute to the total profit.

The constraint

The input is an array prices, where prices[i] is the stock price on day i. I can buy and sell on the same day. However, I can hold only one stock at a time. The goal is the maximum profit from all valid transactions.

When prices rise on consecutive days, a sale and a new purchase at the same price preserve the total profit. For example, consider the gain from day 1 to day 2, then from day 2 to day 3. Their sum equals the gain from day 1 to day 3. Thus, the algorithm only needs the positive differences between adjacent prices.

I initially expected to track each purchase and sale. But a price decrease contributes nothing to the profit. We can split a sequence of price increases at any point without a change to its total gain. The sum of the positive differences gives that gain and satisfies the limit of one stock at a time.

For [7, 1, 5, 3, 6, 4], the increases are 1 → 5 and 3 → 6, so the total profit is 4 + 3 = 7.

Greedy implementations

The one pass implementation is:

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

For the same example, the adjacent changes are:

• 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)

The total profit is 4 + 3 = 7.

Every positive adjacent difference belongs to some increasing run. Adding the differences in a run is equal to buying at its first price and selling at its last price. Negative differences cannot improve the result, so skipping them is safe. The scan thus produces the maximum profit in one pass.

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
    }
}

Complexity and reusable pattern

I initially expected to need dynamic programming, but the greedy approach is sufficient. The algorithm runs in O(n) time and O(1) space.

The useful pattern is to add each local gain when the problem allows unlimited non overlapping transactions. Before reaching for dynamic programming, check whether a sequence of local choices already accounts for the global result.