Contiguous Array Sum

Hello! Today I'm going to to take you through an interesting toy problem that has known to show up in coding interviews. The goal is to create a function called contiguous or maximum array sum, that takes in an array of any size containing both positive and negative integers, and outputs the largest sum of contiguous numbers, which could be a single number or a series of numbers in the array.

What's interesting about this problem is that it can be solved surprisingly fast (magic) using a key principle that is found all across the wide world of programming. The key is to solve the larger big-picture problem by breaking it down into the smallest possible example of the problem. While we aren't necessarily going to recurse in the solution, we use this principle to save computation time and avoid unnecessary calculations.If we can solve the problem in an optimal sub-structure, the
solution will remain the same in the larger example.

So to solve this problem, you must use an array of integers with mixed signs, as a an array of positive integers will always have the entire set as the largest contiguous sum.

The brute force method was what came to mind when I first saw this problem, which was checking every number with every other number and then comparing each sum to find the largest sum.

So here's our input:

[-1, 3, 3, 4, -2, 0]

A contiguous sub array can be any length, but it must be a subset of the original array and have the items in their respective order without any breaks.

And if we use Kadane's algorithm, we can get an O(n) solution rather than the quadratic time complexity the brute force method gives us. This algorithm saves the value of the previous contiguous sub array sum as the best sum, so that the current sum can be immediately compared to it during the initial loop through the number. Having to not compute the sum for the entire sub array each time, we can simply add the next number to the previous sum.

We loop through the numbers and keep track of the current and best sums,
and after the loop passes one time, we can deduce our answer for this problem.

And here's the final code solution:

let currentSum = 0;
  let bestSum = nums[0];

  nums.forEach(num => {
    currentSum = Math.max(num, currentSum + num);
    bestSum = Math.max(bestSum, currentSum);
  });

  return bestSum;