//通過每次與前一位的最大連續(xù)子串的信息做比較進行拼接

function getTempByPrevSeq(PrevTemp, currentValue) {

    //這里規(guī)定，0也可以進行子串拼接

    if (PrevTemp.sum >= 0) {

        return {

            num: PrevTemp.num + 1,

            sum: PrevTemp.sum + currentValue

        };

    } else {

        return {

            num: 1,

            sum: currentValue

        }

    }

}

function getMaxSumSeqArr(input) {

    if (input.length === 0) return;

    var temps = []; // 存儲每一位與前面連續(xù)之后可得最大值的信息，以便后面的每一位進行迭代更新

    //第一位向前的最大子串就是它自己本身

    var temp = {

        num: 1,

        sum: input[0]

    };

    temps.push(temp);

    for (var i = 1, len = input.length; i < len; i++) {

        var ref = input[i];

        //從前向后迭代

        var temp = getTempByPrevSeq(temps[i-1], ref);

        temps.push(temp);

    }

    //存儲了迭代過程中的信息, 可以在這里看看

    console.log(temps);

    var maxValue, //獲取最大值

        indexArr = []; //獲取多個結(jié)果的index

    maxValue = temps[0].sum;

    indexArr.push(0);

    for (var i = 1, len = temps.length; i < len; i++) {

        var ref = temps[i];

        if (ref.sum === maxValue) {

            indexArr.push(i);

        } else if (ref.sum > maxValue) {

            maxValue = ref.sum;

            indexArr.length = 0; //重置數(shù)組

            indexArr.push(i);

        }

    }

    //output

    console.log("MaxValue: " + maxValue);

    for (var i = 0, len = indexArr.length; i < len; i++) {

        var index     = indexArr[i],

            ref     = temps[index];

        console.log(input.slice(index-ref.num+1, index+1));

    }

}

var input = [-2, 1, -3, 4, -1, 2, 1, -5, 4];

getMaxSumSeqArr(input);

該算法效率為o(n)。
對于每一位數(shù)，先取出前一位的信息進行判斷前面連續(xù)子串的總和，如果總和大于等于0，則將自己與前面進行拼接，否則只保留自身，以此生成處理信息傳遞給下一位處理。