Find max subarray of an array

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

The problem was first posed by Ulf Grenander of Brown University in 1977, as a simplified model for maximum likelihood estimation of patterns in digitized images. 

Here we share three methods to find the max subarray of an array using JavaScript.

1. Brute force method

We can try every combination of elements in the array to get the max subarray. The code is :

function findMaxSubArrayWithBruteForce(arr){
    var maxSum=0,max=Number.NEGATIVE_INFINITY,leftIndex=0,rightIndex=arr.length-1;
    for(var i=0,len=arr.length;i<len;++i){
        maxSum=0;
        for(var j=i;j<len;++j){
            maxSum+=arr[j];
            if(max<maxSum){
                leftIndex=i;
                max=maxSum;
                rightIndex=j;
            }
        }
    }
    return {left:leftIndex,right:rightIndex,sum:max};
}

For the above method, it will take O(n²) time.

2. Divide and conquer

Suppose we want to find a maximum subarray of the subarray A[low .. high]. Divide-and-conquer suggests that we divide the subarray into two subarrays of as equal size as possible. That is, we find the midpoint, say mid, of the subarray, and consider the subarrays A[low..mid] and A[mid+1..high. Any contiguous subarray A[i.. j] of A[low..high] must lie in exactly one of the following places:

• entirely in the subarray A[low..mid], so that low <= i<= j<=mid,
•  entirely in the subarray A[mid+1..high], so that mid < i<= j<=high, or
•  crossing the midpoint, so that low <= i <=mid < j<=high.

Therefore, a maximum subarray of A[low..high] must lie in exactly one of these places.

Here is the code:

function findMaxCrossingSubArray(arr,left,mid,right){
    var leftMax=Number.NEGATIVE_INFINITY;
    var leftIndex=mid;
    var leftSum=0;
    for(var i=mid;i>=left;--i){
        leftSum+=arr[i];
        if(leftMax<leftSum){
            leftMax=leftSum;
            leftIndex=i;
        }
    }
    var rightMax=Number.NEGATIVE_INFINITY;
    var rightIndex=mid+1;
    var rightSum=0;
    for(var j=rightIndex;j<=right;++j){
        rightSum+=arr[j];
        if(rightMax<rightSum){
            rightMax=rightSum;
            rightIndex=j;
        }
    }
    return {left:leftIndex,right:rightIndex,sum:(leftMax+rightMax)};
}

function findMaxSubArray(arr,leftIndex,rightIndex){
    if(leftIndex===rightIndex){
        return {left:leftIndex,right:rightIndex,sum:arr[leftIndex]};
    }else{
        var midIndex=Math.floor((leftIndex+rightIndex)/2);
        var leftSum=findMaxSubArray(arr,leftIndex,midIndex);
        var rightSum=findMaxSubArray(arr,midIndex+1,rightIndex);
        var crossSum=findMaxCrossingSubArray(arr,leftIndex,midIndex,rightIndex);
        if(leftSum.sum>=crossSum.sum&&leftSum.sum>=rightSum.sum){
            return leftSum;
        }else if(crossSum.sum>=leftSum.sum&&crossSum.sum>=rightSum.sum){
            return crossSum;
        }else{
            return rightSum;
        }
    }
}

The cost for above method is O(nlgn).

3. Kadane's algorithm

Kadane's algorithm consists of a scan through the array values, computing at each position the maximum subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position.

function findMaxSubArrayLinear(arr){
    var maxEndingHere=arr[0],maxSoFar=arr[0],leftIndex=rightIndex=0;
    for(var i=1,len=arr.length;i<len;++i){
        if(maxEndingHere<0){
            leftIndex=i;
            maxEndingHere=arr[i];
        }else{
            maxEndingHere+=arr[i];
        }
        
        if(maxEndingHere>maxSoFar){
            rightIndex=i;
            maxSoFar=maxEndingHere;
        }
    }
    return {left:leftIndex,right:rightIndex,sum:maxSoFar};
}

The cost for this method is O(n).