largestSubsequence.js

function subsequenceWithLargestSum(xs) {
    var n = xs.length;

    var start = 0;
    var runningSum = 0;
    var largestStart = 0;
    var largestEnd = 0;
    var largestSum = 0;

    for (var i = 0; i < n; i++) {
        var x = xs[i];

        if (x >= 0) {
            runningSum += x;
        } else {
            // as the sum of the subsequence is about to go down, remember this as the largest
            // subsequence seen if it is larger than the previous sum
            if (runningSum > largestSum) {
                largestSum = runningSum;
                largestStart = start;
                largestEnd = i;
            }

            if (runningSum + x >= 0) {
                // keep the start, as adding this subsequence will only make it LARGER
                runningSum += x;
            } else {
                // the subsequence heretofore is now NEGATIVE, so do not carry on with it
                start = i + 1;
                runningSum = 0;
            }
        }
    }

    return {
        sum: largestSum,
        start: largestStart,
        end: largestEnd,
        subsequence: xs.slice(largestStart, largestEnd)
    };
}