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

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.