Simple stock trading backtesting

You're building a high frequency trading algorithm and need a baseline to measure its performance. The backtesting setup is straightforward: given an array of closing prices for a stock over several days, calculate the maximum profit achievable by buying and selling as many times as you want, with the constraint that you must sell before buying again. This problem is also known as "Best Time to Buy and Sell Stock II" on other platforms, and it's a staple at companies like Facebook and Bloomberg.

TL;DR

Sum every positive consecutive price difference. If today's price is higher than yesterday's, add the difference to your running profit total. This greedy approach captures every upward price movement in a single O(n) pass with O(1) space. The key realization is that any multi-day profitable trade can be decomposed into a series of single-day gains, so you never need to look ahead or track buy/sell points explicitly.

Why This Problem Matters

Stock trading problems form one of the most popular families of array questions in technical interviews. The single-transaction variant (Stock I) tests tracking a running minimum. This multi-transaction variant tests whether you can recognize that a greedy strategy works when there are no constraints on the number of trades. It's a clean example of how greedy algorithms can replace seemingly complex optimization problems.

Understanding the Problem

Given closing prices of a stock over n days, find the maximum profit with these rules:

• You can buy and sell as many times as you want
• You must sell before buying again (no stacking positions)
• No brokerage fees
• If prices only decline, return 0
• The array has at least two elements

Here's the test case from the problem: [0, 50, 10, 100, 30]

Looking at these prices, the optimal strategy is to buy at 0 and sell at 50 (profit: 50), then buy at 10 and sell at 100 (profit: 90), for a total of 140.

Why Not Just Find the Global Min and Max?

A tempting first instinct is to buy at the lowest price and sell at the highest. For [0, 50, 10, 100, 30], that would mean buying at 0 and selling at 100 for a profit of 100. But by making two trades instead, you capture 140.

The difference comes from the dip between days 1 and 2. By selling at 50 before the drop and buying again at 10, you avoid losing 40 and then ride the next wave up.

Edge Cases

1. Continuous decline [100, 40, 20, 10]: Every day is lower than the previous. No profitable trade exists, so return 0.
2. Flat prices [1, 1]: No price movement means no profit. Return 0.
3. Continuous rise [10, 20, 30, 40]: Every day is higher than the last. The total profit equals the difference between the last and first price.
4. Alternating pattern [0, 100, 0, 100, 0, 100]: Buy at every 0, sell at every 100, for maximum profit of 300.

Solution Approach

The Greedy Insight

Any profitable trade spanning multiple days can be broken down into single-day trades. Consider buying on day 2 and selling on day 5:

profit = prices[5] - prices[2]
       = (prices[3] - prices[2]) + (prices[4] - prices[3]) + (prices[5] - prices[4])

This telescoping sum means a multi-day gain is exactly the sum of each day-over-day gain within that period. So instead of tracking buy and sell points, simply sum all positive consecutive differences.

Algorithm

1. Initialize profit to 0
2. For each day starting from day 1, compute twoDayProfit = prices[i] - prices[i-1]
3. If twoDayProfit is positive, add it to profit
4. Return profit

That's the entire algorithm. One pass, constant space.

Walkthrough

For [0, 50, 10, 100, 30]:

The algorithm processes each day exactly once. On days where the price went up (day 1 and day 3), it adds the gain. On days where the price dropped (day 2 and day 4), it skips. Final profit: 140.

Down Market Walkthrough

For [100, 40, 20, 10]:

Every consecutive difference is negative, so nothing gets added. The algorithm returns 0, which is the correct strategy when there are no profitable trades.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int maxProfit(int[] closingPrices) {
    // Initialize total profit to 0
    int profit = 0;

    // Check each consecutive pair of days
    for (int i = 1; i < closingPrices.length; i++) {
      // Calculate gain/loss from yesterday to today
      int twoDayProfit = closingPrices[i] - closingPrices[i - 1];

      // Only accumulate gains, ignore losses
      if (twoDayProfit > 0) {
        profit += twoDayProfit;
      }
    }

    return profit;
  }
}

The solution is remarkably short. The for loop starts at index 1 and compares each price with the previous day. Positive differences accumulate into profit. Negative differences are simply ignored, which is equivalent to not trading on those days.

Complexity Analysis

Time Complexity: O(n)

The algorithm iterates through the price array exactly once. Each iteration performs a subtraction, a comparison, and possibly an addition, all O(1) operations. With n days of prices, the total work is O(n).

Space Complexity: O(1)

Only two variables are used regardless of input size: profit for the running total and twoDayProfit for the day-over-day difference. No additional arrays or data structures are allocated.

Why Greedy Works Here

Greedy algorithms don't always produce optimal results, but they do here because:

• Every upward price movement is independent and additive
• There's no penalty for trading (no fees, no cooldown)
• You can always sell and immediately rebuy

If the problem added transaction fees or cooldown periods, the greedy approach would break down and you'd need dynamic programming instead.

Common Pitfalls

1. Trying to find optimal buy/sell pairs: This overcomplicates the solution. You don't need to track when you buy or sell, just sum the positive differences.

2. Single-transaction thinking: If you've recently solved Stock I (single transaction), you might try to adapt that approach. Stock II requires a fundamentally different strategy.

3. Forgetting negative differences: Make sure to only add positive differences. Adding all differences would give you prices[n-1] - prices[0], which is just one trade from start to end.

4. Off-by-one errors: The loop starts at index 1, not 0. Starting at 0 would cause an array index out of bounds when accessing closingPrices[i - 1].

Interview Tips

When solving this in an interview:

1. Clarify the constraints: Ask about fees, cooldown periods, and minimum holding time. These change the problem significantly.

2. Start with examples: Work through a small array like [1, 5, 3, 8] to demonstrate your understanding. Show that buying at 1, selling at 5, buying at 3, selling at 8 gives profit of 4 + 5 = 9.

3. Explain the telescoping property: This is the core insight that justifies the greedy approach. Mention that prices[j] - prices[i] equals the sum of consecutive differences between i and j.

4. Mention follow-ups: Show awareness of the Stock III (at most 2 transactions) and Stock IV (at most k transactions) variants, which require dynamic programming.

Key Takeaways

• Summing all positive consecutive differences captures every profitable trading opportunity, because any multi-day gain telescopes into single-day gains.
• The greedy approach works here specifically because there are no transaction fees or cooldown constraints. Adding either of those requires dynamic programming.
• This runs in O(n) time and O(1) space, which is optimal since you must read every price at least once.
• Don't confuse this with the single-transaction variant (Stock I), which tracks a running minimum. The multi-transaction variant is simpler once you see the greedy property.
• In interviews, always clarify constraints first. The stock trading family has at least six variants, and the optimal approach differs for each.

Practice and Related Problems

Once you're comfortable with this problem, try these related challenges to strengthen your greedy and array skills:

• Max Profit (single transaction variant)
• Subarray with Maximum Total (Kadane's algorithm, another greedy classic)
• Leap to the Finish Line (greedy decision-making on arrays)

This problem and many others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. Consistent practice with greedy problems like this one builds the pattern recognition that makes interview day feel routine rather than stressful.

Solutions in Other Languages

Python

class Solution:
    def max_profit(self, closing_prices):
        profit = 0
        for i in range(1, len(closing_prices)):
            two_day_profit = closing_prices[i] - closing_prices[i - 1]
            if two_day_profit > 0:
                profit += two_day_profit
        return profit

JavaScript

class Solution {
  maxProfit(closingPrices) {
    let profit = 0;
    for (let i = 1; i < closingPrices.length; i++) {
      const twoDayProfit = closingPrices[i] - closingPrices[i - 1];
      if (twoDayProfit > 0) profit += twoDayProfit;
    }
    return profit;
  }
}

TypeScript

class Solution {
  maxProfit(closingPrices: number[]): number {
    let profit = 0;
    for (let i = 1; i < closingPrices.length; i++) {
      const twoDayProfit = closingPrices[i] - closingPrices[i - 1];
      if (twoDayProfit > 0) profit += twoDayProfit;
    }
    return profit;
  }
}

C++

#include <vector>

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

Go

func (s *Solution) MaxProfit(closingPrices []int) int {
    profit := 0
    for i := 1; i < len(closingPrices); i++ {
        twoDayProfit := closingPrices[i] - closingPrices[i-1]
        if twoDayProfit > 0 {
            profit += twoDayProfit
        }
    }
    return profit
}

Scala

class Solution {
  def maxProfit(closingPrices: Array[Int]): Int = {
    var profit = 0
    for (i <- 1 until closingPrices.length) {
      val twoDayProfit = closingPrices(i) - closingPrices(i - 1)
      if (twoDayProfit > 0) profit += twoDayProfit
    }
    profit
  }
}

Kotlin

class Solution {
    fun maxProfit(closingPrices: IntArray): Int {
        var profit = 0
        for (i in 1 until closingPrices.size) {
            val twoDayProfit = closingPrices[i] - closingPrices[i - 1]
            if (twoDayProfit > 0) {
                profit += twoDayProfit
            }
        }
        return profit
    }
}

Swift

class Solution {
    func maxProfit(_ closingPrices: [Int]) -> Int {
        var profit = 0
        for i in 1..<closingPrices.count {
            let twoDayProfit = closingPrices[i] - closingPrices[i - 1]
            if twoDayProfit > 0 {
                profit += twoDayProfit
            }
        }
        return profit
    }
}

Rust

impl Solution {
    pub fn max_profit(&self, closing_prices: Vec<i32>) -> i32 {
        let mut profit = 0;
        for i in 1..closing_prices.len() {
            let two_day_profit = closing_prices[i] - closing_prices[i - 1];
            if two_day_profit > 0 {
                profit += two_day_profit;
            }
        }
        profit
    }
}

Ruby

class Solution
  def max_profit(closing_prices)
    profit = 0
    (1...closing_prices.length).each do |i|
      two_day_profit = closing_prices[i] - closing_prices[i - 1]
      profit += two_day_profit if two_day_profit > 0
    end
    profit
  end
end

C#

public class Solution {
    public int maxProfit(int[] closingPrices) {
        int profit = 0;
        for (int i = 1; i < closingPrices.Length; i++) {
            int twoDayProfit = closingPrices[i] - closingPrices[i - 1];
            if (twoDayProfit > 0) {
                profit += twoDayProfit;
            }
        }
        return profit;
    }
}

Dart

class Solution {
  int maxProfit(List<int> closingPrices) {
    int profit = 0;
    for (int i = 1; i < closingPrices.length; i++) {
      int twoDayProfit = closingPrices[i] - closingPrices[i - 1];
      if (twoDayProfit > 0) {
        profit += twoDayProfit;
      }
    }
    return profit;
  }
}

PHP

class Solution {
    public function maxProfit(array $closingPrices): int {
        $profit = 0;
        for ($i = 1; $i < count($closingPrices); $i++) {
            $twoDayProfit = $closingPrices[$i] - $closingPrices[$i - 1];
            if ($twoDayProfit > 0) {
                $profit += $twoDayProfit;
            }
        }
        return $profit;
    }
}