How to find the largest contiguous sum in a one-dimensional array

JavaScript, algorithms, arrays, dynamic programming

Here is one way to determine the largest contiguous sum in a one dimensional array.

Time complexity: O(n)
Space complexity: O(n)

largestContiguousSumTry in REPL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function largestContiguousSum(array) {
  if (!array.length) return -Infinity;
    if (array.length === 1) return array[0];
    const T = [array[0]];
    
  // Fill T with largest contiguous sum possible at index i
  for (let i = 1; i < array.length; i++) {
      const num = array[i];
      T[i] = Math.max(num, T[i-1]+num); // largest sum at index i will either be the number itself or the previous max + current number
  }
  
  const answer = T.reduce((max, num) => max > num ? max : num, -Infinity);
  
  return answer;
}

Tests can be found at REPL.it