Kadane's Algorithm not returning correct value for largest consecutive sum?

Question

Trying to use Kadane's Algorithm as explained here: https://www.youtube.com/watch?v=OexQs_cYgAQ&t=721s

On this array of numbers: [-5, 10, 2, -3, 5, 8, -20].

The answer is 10 + 2 – 3 + 5 + 8 = 22

---

However when I run the following code I get this:

sumArray = [ 0, 20, 24, 24, 28, 44, 44 ]

No idea how 24 and higher numbers gets in there :( and 22 is missing.

Code below:

const myArray = [-5, 10, 2, -3, 5, 8, -20];

const findMaxConsecutiveSum = (arr) => {
  const sumArray = [];
  let max_so_far = 0;
  let max_ending_here = 0;

  for (let i = 0; i < arr.length; i++) {
    max_ending_here = max_ending_here + arr[i];
    // console.log('position:', i, arr[i]);
    // console.log(max_ending_here = max_ending_here + arr[i]);
    // console.log('max_ending_here', max_ending_here);

    if (max_ending_here < 0) {
      max_ending_here = 0;
    }
    else if (max_so_far < max_ending_here) {
      max_so_far = max_ending_here;
    }

    // console.log('max_so_far', max_so_far);
    sumArray.push(max_so_far);
  }

  return sumArray;
}

console.log(findMaxConsecutiveSum(myArray));

The idea is I just fill up sumArray then filter it by the largest number. However I don't get 22 and instead a ton of larger numbers?

Any ideas why?

Answer 1

You're making the implementation a lot more complicated than it needs to be. From the post on Kadane's algorithm, the code should look something like the following:

def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

The algorithm as stated there wants a single number to be returned, not an array. Translated to JS, that would look like:

const myArray = [-5, 10, 2, -3, 5, 8, -20];
const findMaxConsecutiveSum = (arr) => {
  let max_so_far = 0;
  let max_ending_here = 0;
  for (let i = 0; i < arr.length; i++) {
    max_ending_here = Math.max(arr[i], max_ending_here + arr[i]);
    max_so_far = Math.max(max_so_far, max_ending_here)
  }
  return max_so_far;
}
console.log(findMaxConsecutiveSum(myArray));

Note that the reassignment of max_ending_here requires calling Math.max on arr[i] and max_ending_here + arr[i].