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.

This will take care of both situations mixed array and all negative number array.

var maximumSubArray = function(arr) {
    var max_cur=arr[0], max_global = arr[0];
    for (var i = 1; i < arr.length; i++) {
        max_cur = Math.max(arr[i], max_cur + arr[i]);
        max_global = Math.max(max_cur, max_global);
    }  
    return max_global;
};
console.log(maximumSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maximumSubArray([-10, -11, -12]));

look at this link, it gives a clear explanation for Kadane's algorithm.

Basically you have to look for all positive contiguous segments of the array and also keep track of the maximum sum contiguous segment until the end. Whenever you find a new positive contiguous segment, it checks if the current sum is greater than the max_sum so far and updates that accordingly.

The following code handles the case when all the numbers are negative.

int maxSubArray(int a[], int size)
{
   int max_so_far = a[0], i;
   int curr_max = a[0];

   for (i = 1; i < size; i++)
   {
        curr_max = max(a[i], curr_max+a[i]);
        max_so_far = max(max_so_far, curr_max);
   }
   return max_so_far;
}