Find min and max of cumulative sum in Linq

Question

I have the following function which I am using to find the terminal accumulative positive and negative value, which is working:

public class CumulativeTotal
{
    [Test]
    public void CalculatesTerminalValue()
    {
        IEnumerable<decimal> sequence = new decimal[] { 10, 20, 20, -20, -50, 10 };

        var values = FindTerminalValues(sequence);
        Assert.That(values.Item1, Is.EqualTo(-20));
        Assert.That(values.Item2, Is.EqualTo(50));

        Assert.Pass();
    }

    public static Tuple<decimal,decimal> FindTerminalValues(IEnumerable<decimal> values)
    {
        decimal largest = 0;
        decimal smallest = 0;
        decimal current = 0;

        foreach (var value in values)
        {
            current += value;
            if (current > largest)
                largest = current;
            else if (current < smallest)
                smallest = current;
        }

        return new Tuple<decimal, decimal>(smallest,largest);
    }
}

However, in the interests of learning, how could i implement with Linq?

I can see a package MoreLinq, but not sure where to start!

Answer 1

The major flaw in the code you've presented is that if the running sum of the the sequence stays below zero or above zero the whole time then the algorithm incorrectly returns zero as one of the terminals.

Take this:

IEnumerable<decimal> sequence = new decimal[] { 10, 20, };

Your current algorithm returns (0, 30) when it should be (10, 30).

To correct that you must start with the first value of the sequence as the default minimum and maximum.

Here's an implementation that does that:

public static (decimal min, decimal max) FindTerminalValues(IEnumerable<decimal> values)
{
    if (!values.Any())
        throw new System.ArgumentException("no values");
        
    decimal first = values.First();
    
    IEnumerable<decimal> scan = values.Scan((x, y) => x + y);

    return scan.Aggregate(
        (min: first, max: first),
        (a, x) =>
        (
            min: x < a.min ? x : a.min, 
            max: x > a.max ? x : a.max)
        );
}

It uses System.Interactive to get the Scan operator (but you could use MoreLinq.

However, the one downside to this approach is that IEnumerable<decimal> is not guaranteed to return the same values every time. You either need to (1) pass in a decimal[], List<decimal>, or other structure that will always return the same sequence, or (2) ensure you only iterate the IEnumerable<decimal> once.

Here's how to do (2):

public static (decimal min, decimal max) FindTerminalValues(IEnumerable<decimal> values)
{
    var e = values.GetEnumerator();
    if (!e.MoveNext())
        throw new System.ArgumentException("no values");

    var terminal = (min: e.Current, max: e.Current);
    decimal value = e.Current;

    while (e.MoveNext())
    {
        value += e.Current;
        terminal = (Math.Min(value, terminal.min), Math.Max(value, terminal.max));
    }

    return terminal;
}

Answer 2

yes, you can use MoreLinq like this, it has the Scan method.

public static Tuple<decimal, decimal> FindTerminalValues(IEnumerable<decimal> values)
{
    var cumulativeSum = values.Scan((acc, x) => acc + x).ToList();

    decimal min = cumulativeSum.Min();
    decimal max = cumulativeSum.Max();

    return new Tuple<decimal, decimal>(min, max);
}

The Scan extension method generates a new sequence by applying a function to each element in the input sequence, using the previous element as an accumulator. In this case, the function is simply the addition operator, so the Scan method generates a sequence of the cumulative sum of the input sequence.

Answer 3

You can use the Aggregate method in LINQ to achieve this. The Aggregate method applies a function to each element in a sequence and returns the accumulated result. It takes as parameter an initial accumulator object to keep track of the smallest and largest function.

public static Tuple<decimal,decimal> FindTerminalValues(IEnumerable<decimal> values)
{
    return values.Aggregate(
        // Initial accumulator value:
        new Tuple<decimal, decimal>(0, 0),
        // Accumulation function:
        (acc, value) =>
        {
            // Add the current value to the accumulator:
            var current = acc.Item1 + value;
            // Update the smallest and largest accumulated values:
            var smallest = Math.Min(current, acc.Item1);
            var largest = Math.Max(current, acc.Item2);
            // Return the updated accumulator value:
            return new Tuple<decimal, decimal>(smallest, largest);
        });
}

Answer 4

You can try standard Linq Aggregate method:

// Let's return named tuple: unlike min, max 
// current .Item1 and .Item2 are not readable
public static (decimal min, decimal max) FindTerminalValues(IEnumerable<decimal> values) {
  //public method arguments validation
  if (values is null)
    throw new ArgumentNullException(nameof(values));

  (var min, var max, _) = values
    .Aggregate((min: decimal.MaxValue, max: decimal.MinValue, curr: 0m), 
               (s, a) => (Math.Min(s.min, s.curr + a), 
                          Math.Max(s.max, s.curr + a),
                          s.curr + a));

  return (min, max);
}