Finding Local Maxima Over a Dynamic Range

To allow for a window size of 1 without throwing an exception I flipped the before.Enqueue( curVal ); and before.Dequeue(); functions from Jeroen Cranendonk contribution:

public static IEnumerable<Tuple<int, double>> LocalMaxima( IEnumerable<double> source, int windowSize )
{
    // Round up to nearest odd value
    windowSize = windowSize - windowSize % 2 + 1;
    int halfWindow = windowSize / 2;

    int index = 0;
    var before = new Queue<double>( Enumerable.Repeat( double.NegativeInfinity, halfWindow ) );
    var after = new Queue<double>( source.Take( halfWindow + 1 ) );

    foreach( double d in source.Skip( halfWindow + 1 ).Concat( Enumerable.Repeat( double.NegativeInfinity, halfWindow + 1 ) ) )
    {
        double curVal = after.Dequeue();
        if( before.All( x => curVal > x ) && after.All( x => curVal >= x ) )
        {
            yield return Tuple.Create( index, curVal );
        }
        before.Enqueue( curVal );
        before.Dequeue();
        after.Enqueue( d );
        index++;
    }
}

I suggest a few changes to Levy's post...

1) Levy's code threw an exception when the specified values IList was a nearly straight line.

2) I think the index of the peaks in the array is the desired result. Consider for example what would happen if we had two peaks with identical doubles? Ops. Changed to return index of peaks in specified IList.

    public static IList<int> FindPeaks(IList<double> values, int rangeOfPeaks)
    {
        List<int> peaks = new List<int>();
        double current;
        IEnumerable<double> range;

        int checksOnEachSide = rangeOfPeaks / 2;
        for (int i = 0; i < values.Count; i++)
        {
            current = values[i];
            range = values;

            if (i > checksOnEachSide)
            {
                range = range.Skip(i - checksOnEachSide);
            }

            range = range.Take(rangeOfPeaks);
            if ((range.Count() > 0) && (current == range.Max()))
            {
                peaks.Add(i);
            }
        }

        return peaks;
    }

There are probably more efficient ways but LINQ makes this pretty straightforward

    static IList<double> FindPeaks(IList<double> values, int rangeOfPeaks)
    {
        List<double> peaks = new List<double>();

        int checksOnEachSide = rangeOfPeaks / 2;
        for (int i = 0; i < values.Count; i++)
        {
            double current = values[i];
            IEnumerable<double> range = values;
            if( i > checksOnEachSide )
                range = range.Skip(i - checksOnEachSide);
            range = range.Take(rangeOfPeaks);
            if (current == range.Max())
                peaks.Add(current);
        }
        return peaks;
    }

Old question that already has an accepted answer, but I wanted something better than O(n^2). This function is O(n*m) where m is the window size, and has the advantage of actually working, too. The method returns tuples of indices of local maxima and their associated value.

The calls to Enumerable.Repeat() ensure maxima at the very beginning and end of the set are found, as well.

The comparison with the after queue uses >= so that a local maximum will be found at the beginning of a plateau of values. A side effect is that the value at index 0 is returned if all values in the set are equal, which may or may not be desirable.

public static IEnumerable<Tuple<int, double>> LocalMaxima( IEnumerable<double> source, int windowSize )
{
    // Round up to nearest odd value
    windowSize = windowSize - windowSize % 2 + 1;
    int halfWindow = windowSize / 2;

    int index = 0;
    var before = new Queue<double>( Enumerable.Repeat( double.NegativeInfinity, halfWindow ) );
    var after = new Queue<double>( source.Take( halfWindow + 1 ) );

    foreach( double d in source.Skip( halfWindow + 1 ).Concat( Enumerable.Repeat( double.NegativeInfinity, halfWindow + 1 ) ) )
    {
        double curVal = after.Dequeue();
        if( before.All( x => curVal > x ) && after.All( x => curVal >= x ) )
        {
            yield return Tuple.Create( index, curVal );
        }

        before.Dequeue();
        before.Enqueue( curVal );
        after.Enqueue( d );
        index++;
    }
}