# Kadane’s algorithm explained

Consider tracing the values:

```var maximumSubArray = function(array) {
var ans = 0;
var sum = 0;

console.log(ans, sum);
for (var i = 0; i < array.length; i++) {

ans = Math.max(0, ans + array[i]);
sum = Math.max(sum, ans);
console.log(ans, sum, array[i]);
}
console.log(ans, sum);
return sum;

};

maximumSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]);

```

Prints:

```0 0
0 0 -2
1 1 1
0 1 -3
4 4 4
3 4 -1
5 5 2
6 6 1
1 6 -5
5 6 4
5 6

```

The first column is `ans`, which is the sum of the current subarray. The second is `sum`, representing the sum of the greatest seen so far. The third is the element that was just visited. You can see that the contiguous subarray with the largest sum is `4, −1, 2, 1`, with sum `6`.

The example is from Wikipedia.

The following is a translation of the code given in Wikipedia under the paragraph: “A variation of the problem that does not allow zero-length subarrays to be returned, in the case that the entire array consists of negative numbers, can be solved with the following code:” [EDIT: Small bug fixed in the code below]

```var maximumSubArray = function(array) {
var ans = array[0];
var sum = array[0];

console.log(ans, sum);
for (var i = 1; i < array.length; i++) {

ans = Math.max(array[i], ans + array[i]);
sum = Math.max(sum, ans);
console.log(ans, sum, array[i]);
}
console.log(ans, sum);
return sum;

};

```

See that:

```> maximumSubArray([-10, -11, -12])
-10 -10
-10 -10 -11
-10 -10 -12
-10 -10
-10

```

The last number is the expected result. The others are as in the previous example.