Max Subarray

max_subarray

/**
 * Given an array of real numbers,
 * returns  the max contiguous subsequence for which 
 * the sum of the elements is maximized
 * 
 * @param  {Array} arr  input array
 * @return {Array}      slice with maximum sum
 */
function maxSubarray (arr) {
    //start & end indices for our max slice
    var start = 0
    var end = 0

    //initialize max sum to be first el in array
    var rollingSum = arr[0]
    var maxSoFar = arr[0]

    //roll thru the array
    for (var i = 1; i < arr.length; i++) {
        var el = arr[i]
        
        rollingSum += el

        //if rolling sum is less than the current element, 
        //just start fresh with the current element
        if (rollingSum < el) {
            rollingSum = el

            //reset our slice
            start = i
            end = i
        }

        //update sum if we got a bigger one
        if (rollingSum > maxSoFar) {
            maxSoFar = rollingSum
            end += i - end
        }
    }

    return {
        maxSum: maxSoFar,
        slice: arr.slice(start, end + 1)
    }
}

var tests = [
    //{ maxSum: 5, slice: [5] }
    [5],                              
    //{ maxSum: 4, slice: [4] }
    [-5, 4], 
    //{ maxSum: 4, slice: [4] } 
    [4, -5], 
    //{ maxSum: 9, slice: [4,5] } 
    [4, 5, -5], 
    //{ maxSum: 18, slice: [4, 5, -1, 10] } 
    [4, 5, -1, 10], 
    //{ maxSum: 26, slice: [10, 12, 4] } 
    [1, 2, 5, 2, -30, 10, 12, 4], 
    //{ maxSum: 6, slice: [4, -1, 2, 1] }
    [-2, 1, -3, 4, -1, 2, 1, -5, 4], 
]

tests.forEach(function (test) {
    console.log(maxSubarray(test))
})