maximum sum of n consecutive elements of array

Question

How to find the maximum sum of n consecutive numbers of an array? For example if our array is {2,5,3,4,6} and n == 2 then output should be 10 (i.e. 6 + 4).

I am able to get the logic right for small values of array size and small values of n. But when the array size and n are too large like around 10⁵, my code takes a lot of time. Please suggest an optimized approach.

My code snipped:

for(int i = 0; i <= n - h; i++) {
  int count = 0;
  for(int k = i; k < i + h; k++) {
    count = count + arr[k];
  }
  if(i == 0) {
    ans[z] = count;
  } else if(i != 0) {
    if(count < ans[z]) {
      ans[z] = count;
    }
  }
  count = 0;
}

Solution 1

here is my idea: traverse the array from 0 to (array length - N), and determine the sum of next N-item by using the following expression:
sum of next N-item = previous sum - first item in previous sub-array + last item in next sub-array

Example:

Array = {2,5,3,4,6}

when i = 0, sum = (2 + 5) = 7, max sum = 7

when i = 1, sum = 7 - 2 + 3 = 8, since 8 > 7, so max sum = 8

when i = 2, sum = 8 - 5 + 4 = 7, since 7

when i = 3, sum = 7 - 3 + 6 = 10, since 10 > 8, so max sum = 10

below is the sample code in c#

static int GetLargestSum(int[] array, int n)
{
    int largestSum = 0;
    int previousSum = 0;

    for (int i = 0; i <= array.Length - n; i++)
    {
        if (i == 0)
        {
            for (int j = 0; j < n; j++)
            {
                largestSum += array[j];
            }

            previousSum = largestSum;
        }
        else
        {
            int currentSum = previousSum - array[i - 1] + array[i + n - 1];
            if (currentSum > largestSum)
            {
                largestSum = currentSum;
            }
            previousSum = currentSum;
        }
    }

    return largestSum;
}

Solution 2

function maxSubelementsSum(inputArray, count) {
  let maxSum = 0;
  for (let i = 0; i < count; i++) {
    maxSum += inputArray[i];
  }
  let tempSum = maxSum;
  for (let i = count; i < inputArray.length; i++) {
    tempSum = tempSum + inputArray[i] - inputArray[i - count];
    maxSum = Math.max(tempSum, maxSum);

  }
  return maxSum;
}

Solution 3

Using Java 8.

int[] numArr = {1,3,5,6,7,12,14,2,3,4}; 
List<Integer> intList = Arrays.stream(numArr).boxed().collect(Collectors.toList());         
List<Integer> intSumList = new ArrayList<>();
for(int i=0; i<=numArr.length-3; i++)
{
    int intSum = intList.stream().skip(i).limit(3).mapToInt(Integer::intValue).sum();       
    intSumList.add(Integer.valueOf(intSum));
}       
int maxConsecutiveSum = intSumList.stream().reduce(Integer::max).get(); 
System.out.println("Max sum using 3 consecutive integers :"+maxConsecutiveSum);

Solution 4

There are a lot of ways to go about this.
So far the most optimized I could think of is in O(n).
Where you get to traverse the array once.

I used the sliding window pattern in solving this

Here is the main idea behind the solution:

Get the sum of the first n and store in a variable as temporary max

Set your max to the temporary max

Loop through the array

At any point in the loop, substract the previous element from the temporary max

And add the element in the next n index to the temporary max

Finally compare your main max to the temporary max

If the max is lesser then set your max to the temporary max

function maxSubarraySum(array, num){

    let tempMax = 0
    
    for(let i=0; i<num; i++){
        tempMax += array[i] 
    }
    
    let max = tempMax



    for(i=1; i<array.length - (num-1); i++){

        // Substract the element you are at from the max
        // Add the element at the ith + num
        // compare with the max and reinitialize

        let subs = tempMax - array[i-1]

        tempMax = subs + array[i + num - 1]

        if(max < tempMax){
           max = tempMax
        }
          
    }

    return(max)
    
}

View more solutions

Comments

[terryfkjc]

if we sort the array before calculate the sum, we will get 11 instead of 10 in {2,5,3,4,6}

[das-g]

Shouldn't that be "[...] + last item in next sub-array" and consequently in your else block int currentSum = previousSum - array[i - 1] + array[i + n - 1];?

[swap96]

@terryfkjc i would require a more optimized approach as this takes a lot of time for large values of n and array-size.

[terryfkjc]

@swap96 i am not sure how "optimized" you need, have you benchmark in your actual situation? when n is large, and the array is not sorted, the most optimize way should be O(n)

[swap96]

My array size and 'n' can be upto 10^6.

[das-g]

I think the solution proposed here has complexity O(n + (array.Length - n)) == O(n + array size - n) == O(array.Length). Thus, the size of n shouldn't matter. And O(array.Length) is optimal: Without parallelization, you can't get better than that, as you have to read every array element at least once.

[terryfkjc]

@swap96 have you consider to calculate the sum using parallel algorithm? the idea is basically divide the large array into several small array and let multiple cpu to calculate largest sum in sub arrays at same time.

[Peter Cordes]

I would have written it with the intro sum-the-first-n loop outside the sliding-window loop (which would start with i = 1). You want the compiler to restructure it that way anyway. Also, @das-g is right: you have a bug in your sliding-window. The element you subtract must be n+1 away from the one you're adding. Currently, it's always a distance of 2.

[terryfkjc]

@PeterCordes thanks for the correction, there is a bug in getting the last element in the next sub array

[Peter Cordes]

re: parallelism: I posted an answer with some ideas about threading, and vectorizing the sum of the first window. (And vectorizing the whole operation if you want to check 4 consecutive values of n.)

[stgatilov]

Perhaps it is possible to compute prefix sums with SSE/AVX, and then we can easily compute max(S[i+n] - S[i]) in vectorized way.

[Peter Cordes]

@stgatilov. Prefix sums would be useful if you could generate them on the fly as your array was being written, or if you wanted several different window sizes. Otherwise I think a 2-pass algo would be doomed to failure by memory bandwidth unless it fit in L2 (256k). And also, I don't think prefix sums can vectorize, because there's no independence between elements. Every p[i] needs to see a[i-i], a[i-2], etc. so you need a horizontal operation at every step. I think it's the same problem as trying to vectorize the sliding window directly.

[Peter Cordes]

@stgatilov: Turns out you can SIMD a prefix sum, but it takes a lot of shuffling. Maybe only worth it for floats, where add latency is higher. See also stackoverflow.com/questions/10587598/…. You can also parallelize prefix sums with threads, but the necessary access pattern doesn't look good for SIMD vectors. http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html.

[Devendra Verma]

if you sort the array then order will not be conserved. and choosing first n elements will not guarantee that it is a contiguous subarray of given array.