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;
}

Answer 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;
}

Answer 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;
}

Answer 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);

Answer 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)
    
}

Answer 5

The main improvement possible for your technique is a sliding window. Integer addition has an inverse, subtraction. This makes it possible to drop elements out of the sum and add new ones, instead of re-computing from scratch. (Terryfkjc's answer demonstrates this).

As Terryfkjc commented on his answer, there's thread-level parallelism to be had. You can have different threads check different parts of the array. If the size of the sliding window is more than half the size of the array, then summing the first n should be threaded. Dividing the work between threads is most tricky when n is about half the size of the array. Much bigger, and it can't slide as far. Much smaller, and most of the work is just the sliding.

If you're targeting a CPU with vector instructions, we can vectorize the initial sum of the first w (window size / width) elements easily enough with SIMD. For example, using x86 SSE (C/C++ intrinsics):

#include <immintrin.h>
const __m128i *array_vec = (__m128i*)array;
__m128i sums = _mm_loadu_si128(array_vec);  // or start with _mm_setzero_si128()

 // careful to get the loop start/end and increment correct,
 // whether you count by vectors (i++) or by elements (i+=4)
 // You may need a scalar cleanup at the end if window width isn't a multiple of the vector width
for (int i=1; i < width/4 ; i+=1) {
    sums = _mm_add_epi32(sums, _mm_loadu_si128(array_vec+i));
    // if you know the input is aligned, and you're going to compile without AVX/AVX2, then do:
    // sums = _mm_add_epi32(sums, array_vec[i]);
}
__m128i hisums = _mm_bsrli_si128(sums, 8);  // get the high 2 elements into the low 2 elements of a separate vector
sums = _mm_add_epi32(sums, hisums);  // one step of horizontal merging.    
hisums = _mm_bsrli_si128(sums, 4);  // actually, pshufd would be faster for this, since it doesn't need a mov to preserve sums.
sums = _mm_add_epi32(sums, hisums);

int window_sum = _mm_cvtsi128_si32(sums);  // get the low 32bit element 

I don't think it's possible to vectorize the sliding-window part. We can't usefully slide 4 separate windows, because every window (vector element) needs to see every array element.

However, if we're interested in 4/8/16 different window sizes (preferably consecutive), then we can do that with vectors. So, at each loop iteration, we have a vector with the current sliding window sum. With SSE4.1 pmaxsd (for signed 32bit ints), we can do

window_max = _mm_max_epi32(window_max, window_sums);

The sliding window operation becomes: add the { a[i], a[i+1], a[i+2], a[i+3] }, while removing the same array element from all 4 vector elements. (Alternatively, broadcast the element to add, and subtract a vector of different elements.)

__m128i add_elements = _mm_loadu_si128((__m128i*)&array[i]);  // load i, i+1, etc.
__m128i sub_element = _mm_cvtsi32_si128(array[i-width-1]);
  sub_element = _mm_shuffle_epi32(sub_element, 0); // broadcast the low element of the vector to the other positions.
  // AVX2: use _mm_broadcastd_epi32
  // AVX512 has a broadcast mode for memory references that can be used with most instructions.  IDK how to use it with intrinsics.
__m128i diff = _mm_sub_epi32(add_elements, sub_element);
window_sums = _mm_add_epi32(window_sums, diff);

Getting the loop start/end conditions right, and accounting for the last few elements correctly, is always the challenge with vectors.

See https://stackoverflow.com/tags/x86/info for more about how to use vectors on x86.

Answer 6

Using sliding window, where window size of 2

arr = [2,5,3,4,6];

sum = 0;
temp_sum = 0;

const add = (a,b) => a+b;

for(let i=0;i<arr.length-1;i++){
  console.log(i, i+2,arr.slice(i,i+2));
  temp_sum = add.apply(null, arr.slice(i,i+2));
  if(sum < temp_sum){
    sum = temp_sum;
  }
}

console.log(sum);

Answer 7

here is a short fast solution :

    s = 0
    arrayMaxConsecutiveSum = (a, k) =>
    Math.max(...
        a.map(x => s += x - ~~a[~--k])
    )

Answer 8

def maxSubarraySum(array, noOfelements):
    start = 0
    sum = 0
    nextElement = 1
    maxSum = []
    while noOfelements < len(array)+1:
        for i in range(start, noOfelements):
            sum += array[i]
        maxSum.append(sum)
        sum = 0
        start = nextElement
        nextElement += 1
        noOfelements += 1
    return max(maxSum) if maxSum else None


def sub(array,ele):
    maxSum = []
    end = ele
    for i in range(len(array)):
        if end <= len(array):
            maxSum.append(sum(array[i:end]))
            end += 1
    return max(maxSum) if maxSum else None

def sub1(array,ele):
    tot = [sum(array[i:ele+i]) for i in range(len(array)) if ele+i <= 
    len(array)]
    return max(tot) if tot else None

if __name__ == '__main__':
    print(maxSubarraySum([-1, -2, -5, -3, -8, -1, -5], 4) == -11)
    print(maxSubarraySum([1, -2, 5, 3, -8, 1, 5], 4) == 7)
    print(maxSubarraySum([1, 2, 5, 3, 8, 1, 5], 4) == 18)
    print(maxSubarraySum([1, 2, 5, 3, 8, 1, 5], 2) == 11)
    print(maxSubarraySum([], 4) == None)

complexity = O(n*n) This will work for all given arrays including negative numbers.

Added one more with O(n) - Sub function

one more using list comprehension. - Sub1 function

Answer 9

Using sliding window technique

int curr_sum = 0, max_sum = 0;
for(int i = 0; i < n; i++)
{
     curr_sum += v[i];
}
max_sum = curr_sum;
for(int i = k; i < v.size(); i++)
{
    curr_sum += v[i] - v[i-k];
    max_sum = max(max_sum, curr_sum);
}

cout<<max_sum;

Time Complexity: θ(n)

Auxiliary Space: O(1)

Explanation: [ 1 8 30 -5 20 7] and n = 3

from 0 to n-1 (0 to 2) curr_sum = 1+8+30 = 39

max_sum = 39

fromr n to v.size()-1 (3 to 5)

curr_sum = prev sum + new element - prev window first element

curr_sum = 39 +(-5)-1 = 33

max_sum = max(39,33) = 39

curr_sum = 33 + 20 - 8 = 45

max_sum = max(39,45) = 45

curr_sum = 45 + 7 - 30 = 22

max_sum = max(45,22) = 45

Answer 10

let's use the sliding window approach, which performs the sum of sub-array of size n, then loop through the array till len(arr) - n and perform a simple comparison, you can consider this solution:

def max_sum(arr, window):
    n = len(arr)

    if (n <= window):
        return -1

    window_sum = sum([arr[i] for i in range(window)])
    maxSum = window_sum

    for i in range(n - window):
        window_sum = window_sum - arr[i] + arr[i + window]
        maxSum = max(window_sum, maxSum)
    
    return maxSum

Answer 11

Simplest of them all

A=list(map(int,input().split(" ")))
n=len(A)
max=0
for i in range(n-1):
    if(A[i]+A[i+1]>max):
        max=A[i]+A[i+1]
print(max)

Answer 12

Simply we can iterate the array and find the sum of two consecutive numbers

let array = [2,5,3,4,6];
let sum=0;
let maxNumber = 0;
for(let i=0; i<array.length;i++){
    sum = array[i] + array[i+1];
    if(sum >= maxNumber){
        maxNumber = sum;
    }
    
}
console.log("max of two digit :", maxNumber);

Answer 13

The first thing I would suggest you is sorting the array using mergesort, this has a complexity time of O(n log(n)) then you only have to find the first n consecutive numbers iterating the array from the higher number to the lower one keeping the sum of the current consecutive numbers and this will take a complexity time of O(n). Greetings