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

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 2

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 3

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

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 6

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 7

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 8

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 9

here is a short fast solution :

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

Answer 10

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 11

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 12

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