https://practice.geeksforgeeks.org/problems/kadanes-algorithm/0

kadanes-algorithm.js

// https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
// https://practice.geeksforgeeks.org/problems/kadanes-algorithm/0
function maxSubArraySum(arr, len) {
  let maxSoFar = Math.min(...arr);
  let maxEndingHere = 0;
  let idx;
  for (idx = 0; idx < len; idx++) {
    maxEndingHere = maxEndingHere + arr[idx];
    if (maxSoFar < maxEndingHere) {
      maxSoFar = maxEndingHere;
    }
    if (maxEndingHere < 0) {
      maxEndingHere = 0;
    }
  }
  return maxSoFar;
}
const nums1 = [1,2,3,-2,5];
const result1 = maxSubArraySum(nums1, nums1.length);
console.log(result1, result1 === 9);
const nums2 = [-1,-2,-3,-4];
const result2 = maxSubArraySum(nums2, nums2.length);
console.log(result2, result2 === -1);
const example = [-2,-3,4,-1,-2,1,5,-3];
const resultEx = maxSubArraySum(example, example.length);
console.log(resultEx, resultEx === 7);