求数组的最大子数组 动态规划 时间复杂度O(n) 空间复杂度

2019-03-24  本文已影响0人  RedLee666
function maxSonArray(array) {
    let sum = -Infinity, all = -Infinity, start, end;
    for (let i = 0; i < array.length; i++) {
        if (sum + array[i] > array[i]) {
            sum += array[i];
        } else {
            sum = array[i];
            array[i] > all ? start = i : undefined;
        }
        if (sum > all) {
            all = sum;
            end = i;
        }
    }
    return { start: start, end: end, all: all };
}

写得不好的地方希望大佬指正
上一篇 下一篇

猜你喜欢

热点阅读