Fastest way to find max sum range in int[]

Question

Been optimizing an algorithm and came down to the last part. I have an array of integers like this:

[ 1, 1, 2, 5, 0, 5, 3, 1, 1 ]

My requirement are as follows:

1. input: numbers of integers to sum over
2. the max sum should consist of integers next to each other
3. if an integer has the value 0 the sum in the range would be invalid
4. the max sum of integers and the index of each integer is returned

Expected results:

Given input of 2 (2 wanted) with the array as mentioned should therefor return [ 8, [ 5, 6 ] ] where 8 being the sum of integers at index 5 and 6

Given input of 3 (3 wanted) with the array as mentioned should therefor return [ 9, [ 5, 6, 7 ] ] where 9 being the sum of integers at index 5, 6 and 7 (notice that even though integers at indexes 3, 4, 5 have a higher sum the result is invalid due to index 4 being 0)

I'm currently managing this by doing a lot of looping, but was wondering if somebody had a better way of achieving this. My coding language of choice is currently C# - I would therefor appreciate if possible replies would be in C#. Any use of linq and other fancy Math features is ok as long as it's the fastest way.

Answer 1

I think you can solve this in linear time. First, replace all 0s with a very small number (-2^30 for example) so that it won't affect our sum.

Then:

let s[i] = sum of first i integers
let k = number of integers required
let max = -inf    
for ( int i = k; i <= N; ++i )
  if ( s[i] - s[i - k - 1] > max )
     max = s[i] - s[i - k - 1]

You can probably avoid replacing zeros with a few extra conditions. if s[i] = sum of first i integers, then s[i] - s[k - 1] gives you the sum of the integers k through i.

Edit: You can do this in O(1) extra space like this: first replace all 0s.

then:

max = cr = sum of first k integers.
for ( int i = k + 1; i <= N; ++i )
{
  cr = cr + numbers[i] - numbers[i - k] 
  if ( cr > max )
    max = cr; // also update positions
}

To avoid replacing zeroes in the first solution, just skip k spaces ahead when encountering a zero. In the second solution, skip k or k + 1 (depends on how you choose to implement this special case) spaces ahead, but be sure to rebuild your cr variable when doing the skip!

Answer 2

The below code should do the trick. The performance will depend on the size of the range to be sum'ed. The more elemnts the better it will perform compared to the naïve of adding a subset in every iteration

 int getSum(int[] arr, int wanted)
        {
            var pre = new int[arr.Length];
            pre[0] = 0;
            pre[1] = arr[0];
            int max = 0;
            int skip = 1;
            for (var i = 1; i < arr.Length; i++)
            {
                skip--;
                //if the sum is marked invalid with a zero skip
                var current = arr[i];
                //calculate the index once
                int preIndex = i + 1;
                if (current == 0)
                {
                    skip = wanted;
                    pre[preIndex] = pre[i];
                    continue;
                }
                //store the sum of all elements until the current position
                pre[preIndex] = pre[i] + current;
                //find the lower end of the range under investigation now
                var lower = i - wanted;
                //if we haven't reached the wanted index yet we have no sum or if 
                //it's less than wanted element since we met a 0 
                //just go to the next element
                if (lower < 0 || skip > 0)
                    continue;
                var sum = pre[preIndex] - pre[lower];
                if (sum > max)
                    max = sum;
            }
            return max;
        }

Answer 3

The following was a rant, and totally untested. Not even sure if it will compile. I leave it to others to improve it.

using System;
using System.Linq;
public int[] max(int[] a, int amount) {
    var max = int.MinValue;
    var maxPos = 0;
    if (a.length < amount) return null;
    var c = 0;
    while (c == 0) {
        for (int i = 0; i < amount; i++) {
            if (a[i + maxPos] == 0) {
                c = 0;
                break; // try again
            }
            c += a[i];
        }
        if (c != 0) maxPos = i - amount;
    }
    if (c == 0) return null;
    max = c;
    for (int i = maxPos; i + amount < a.length; i++) {
        if(a[i] == 0) {
            i += amount - 1;
            continue;
        }
        c -= a[i];
        c += a[i + amount];
        if (c > max) {
            c = max;
            maxPos = i;
        }
    }
    if (c == 0) return null;
    var result = new int[amount + 1];
    result[0] = max;
    for (int i = 0; i < amount; i++)
        result[i + 1] = maxPos + i;
    return result;
}

Answer 4

Is "easy to read" code considered an "optimization"?

int numberOfElements = 4;   //parameter
int[] numbers = new[] { 1, 1, 2, 5, 0, 5, 3, 1, 1 };    //numbers


int[] result =
     //cicle each element
    (from n in Enumerable.Range(0, numbers.Length - numberOfElements + 1)
     //keep the (n + numberOfElements) elements
     let myNumbers = from p in Enumerable.Range(n, numberOfElements)
                     select numbers[p]
     //keep the sum (if we got a 0, sum is 0)
     let sum = myNumbers.Contains(0) ? 0 : myNumbers.Sum()
     orderby sum descending     //order by sum
     select myNumbers)          //select the list
        .First().ToArray();     //first is the highest

Consider adding a .AsParallel() for performance when .NET 4 is out.

Answer 5

Idea is 1. Split array to groups to measure sum 2. Count sum for every group 3. Figure out max sum

Here is the code

private Result GetMax(ICollection<int> items, int itemCount)
{
  return items.
    Take(items.Count - (itemCount - 1)).
    Select((value, index) => items.Skip(index).Take(itemCount)).
    Select((group, index) =>
      new Result
      {
        Index = index,
        Sum = group.Aggregate(0, (sum, i) => sum + (i == 0 ? int.MinValue : i))
      }).
    Max();
}

private struct Result : IComparable<Result>
{
  public int Index { get; set; }
  public int Sum { get; set; }

  public int CompareTo(Result other)
  {
    return Sum.CompareTo(other.Sum);
  }
}

Answer 6

This is O(n) time and O(1) space and goes only once through the array.

static public int[] FindMaxSumRange(int[] data, int n)
{
    // two pointers showing the lower and upper bound of current running sum
    int upper = 0, lower = 0;
    // best result found yet
    int max_found = 0;
    int max_position = -1;

    while (lower <= data.Length - n) {
        int running_sum = 0;
        // prefill running sum with n items
        for (upper = lower; upper - lower < n && upper < data.Length; upper++) {
            if (data[upper] == 0) {
                // found a zero, set lower pointer to the next item
                lower = upper + 1;
                break;
            }
            running_sum += data[upper];
        }
        if (upper - lower != n) {
            // found a zero, restart at new lower position
            continue;
        }
        if (running_sum > max_found) {
            max_found = running_sum;
            max_position = lower;
        }
        while (upper < data.Length) {
            if (data[upper] == 0) {
                // found a zero, set lower pointer to the next item
                lower = upper;
                break;
            }
            running_sum += data[upper] - data[lower];
            if (running_sum > max_found) {
                max_found = running_sum;
                max_position = lower;
            }
            upper++; lower++;
        }
        lower++;
    }
    return new int[]{max_found, max_position};
}

This return the max sum and the position it was found at. If you need to get a list of the indices, just build the range [max_position, max_position + n)