JS interview question #2: largest sum for contiguous sequence in array

DanielDecember 7, 2022

Two weeks ago I've started a new section for this blog: the JS interview questions. Hope this will become a fun and useful collection of hand picked Javascript interview questions to prepare for your programming interviews.

💼 Js Interview Question

The past newletter question was: you are given an array of integers (both positive and negative). Find the contiguous sequence with the largest sum. Return the sum and the numbers.

For example:

EXAMPLE:
Input:2, -8, 3, -2, 4, -10
Output: 5 ( i. e • , { 3, -2, 4})

🎓 Solution (Javascript)

Below is the full code for the solution:

let currentMaxSum, start, end = null

const resetGlobals = ()=>  
  currentMaxSum = start = end = null

const printSolution = (ds, start, end) => {
  console.log("-------------")
  console.log(ds)
  console.log(ds.slice(start, end + 1))
  const sum = ds.slice(start, end + 1).reduce(
    (acc, val) => acc += val,
    0
  )
  console.log(sum)
  console.log("-------------")
}

const checkForMaxSum = (sum, startIndex, endIndex) => {
  if ((currentMaxSum != null) && (currentMaxSum > sum))
    return;
  currentMaxSum = sum
  start = startIndex
  end = endIndex
}

const checkSumsWithStartignIndex = (startIndex, ds) => {
  let sum = 0
  for (let endIndex = startIndex; endIndex < ds.length; endIndex++) {
    sum += ds[endIndex]
    checkForMaxSum(sum, startIndex, endIndex)
  }
}

const maxSum = (ds)=> {
  resetGlobals()
  ds.forEach( 
    (el, index)=> checkSumsWithStartignIndex(index, ds)
  )
  printSolution(ds, start, end)
}

Example ussage:

const DS1 = [2, -8, 3, -2, 4, -10]
const DS2 = [-1, -1, 7, -4]
maxSum(DS1)
maxSum(DS2)