[Algorithm] Kadane's Algorithm

Write a function that takes in a non-empty array of integers and returns the maximum sum that can be obtained by summing up all of the integers in a non-empty subarray of the input array. A subarray must only contain adjacent numbers (numbers next to each other in the input array).

Sample Input

array = [3, 5, -9, 1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1, -5, 4]

Sample Output

19 // [1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1]

/*function kadanesAlgorithm(array) {
  return helper(array, -Infinity, 0, 0)
}

function helper(array, max = -Infinity, current, i) {
  if (i > array.length - 1) {
    return max
  }
  const sum = current + array[i];
  return helper(array, Math.max(sum, max), sum < 0 ? 0: sum, i + 1);
}*/

function kadanesAlgorithm(array) {
  let max = -Infinity;
  let current = 0;
  for (let num of array) {
    current = Math.max(current + num , num)
    max = Math.max(current, max)
  }
  return max
}

// Do not edit the line below.
exports.kadanesAlgorithm = kadanesAlgorithm;