Finds the largest sum of sub-arrays, given an array of integers (Not allowing for zero length sub-arrays).

max-subarray-problem.js

function maxContiguousSubArray(array) {
    var maxEndingHere = array[0];
    var maxSoFar = array[0];
    for(var i = 1; i < array.length; i++) {
        maxEndingHere = Math.max(array[i], maxEndingHere + array[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}

function maxNonContiguousSubArray(array) {
    var maximumValue = -Infinity;
    var subArrayValue = array.reduce(function(previousValue, currentValue) {
        var value = (currentValue > 0) ? currentValue : 0;
        maximumValue = Math.max(maximumValue, currentValue);
        return previousValue += value;
    }, 0);
    
    if(maximumValue < 0) {
        return maximumValue;
    } else {
        return subArrayValue;
    }
}

Sourced from:
https://en.wikipedia.org/wiki/Maximum_subarray_problem

Last modified:
03 August 2016

Last accessed:
04 August 2016