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.