Haemin Park | DS & A

Question & Examples

Write a function called maxSubarraySum which accepts an array of integers and a number called n. The function should calculate the maximum sum of n consecutive elements in the array.

// Examples
maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 2)
// 10 (because 8 and 2 are the maximum sum of two consecutive numbers) 
 
maxSubarraySum([], 4)
// null

One easy approach would be to start with the first value, and looping over the first three values. It will look something like this:

function maxSubarraySum(arr, n) {
  if(arr.length === 0) {
    return null
  }
  if(n > arr.length) {
    return null
  }
  // we're using -Infinity as an array could
  // have only negative numbers
  let max = -Infinity
 
  // our loop cannot exceed the length of the array
  for(let i = 0; i < arr.length - n + 1; i++) {
    // we set a temporary value as 0.
    // This value is used to track the added
    // consecutive values
    let temp = 0;
 
    // we loop over the first "n" numbers and add
    // them all up + set it to the temp var
    for(let j = 0; j < n; j++) {
      temp = temp + arr[i + j]
    }
 
    // if the temp value is greater than the
    // original max value, we replace the original
    // max value to the temp value
    if(temp > max) {
      max = temp
    }
    console.log("Temp:", temp)
  }
  return max
}

This solution may be a problem when the length of the array and the value of the n variable gets really big. A better solution would be the one below.

Solution

function maxSubarraySum(arr, n) {
  // initialize variables
  let maxSum = 0
  let tempSum = 0
  if(arr.length < n) {
    return null
  }
 
  // calculate the first "n" numbers first
  for(let i = 0; i < n; i++) {
    maxSum = maxSum + arr[i]
  }
 
  // sync the two vars so they have same value
  tempSum = maxSum
 
  for(let i = n; i < arr.length; i++) {
    // substract the first value of the three consecutive values
    // then add the arr[i] value
    tempSum = tempSum - arr[i - n] + arr[i]
 
    // then compare to see which value is greater
    maxSum = Math.max(maxSum, tempSum)
  }
  return maxSum
}

Time Complexity: O(n)

Calculating the value of the maximum sum of n consecutive elements in an array

Question & Examples

Solution