编辑代码

// 在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。
// 但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？
// 例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。
// 给一个数组，返回它的最大连续子序列的和(子向量的长度至少是1)

function FindGreatestSumOfSubArray(array) {
    // write code here
    return __calMaxSubSumDiv(array, 0, array.length-1);
}

// https://www.cnblogs.com/en-heng/p/3970231.html#分治法
// 思想：分治法
// 时间复杂度：O(nlogn)

function __calMaxSubSumDiv(arr, low, high) {
    if(low > high)
        return 0;

    if(low === high)
        return Math.max(0, arr[low]);
    
    // 中间元素下标，下取整
    let mid = parseInt((low + high) / 2);

    // 计算中间元素往左累加的最大值
    let lmax = 0, lsum = 0;
    for(let i=mid; i>=low; i--) {
        lsum += arr[i];
        lmax = Math.max(lmax, lsum);
    }

    // 计算中间元素往右累加的最大值
    let rmax = 0, rsum = 0;
    for(let i=mid+1; i<=high; i++) {
        rsum += arr[i];
        rmax = Math.max(rmax, rsum);
    }

    // 分治，返回结果
    return Math.max(lmax+rmax,
                __calMaxSubSumDiv(arr, low, mid),
                __calMaxSubSumDiv(arr, mid+1, high));
}

// https://www.cnblogs.com/en-heng/p/3970231.html#动态规划
// 思想：动态规划(扫描法)
// 对于数组a，用c[i]标记子数组arr[0...i]的最大和
// 则有：       c[i] = max{ a[i], c[i-1]+a[i] }
// 或：         c[i] = max{ 0, c[i-1] } + a[i]
// ...
// 子数组最大和即max c[i]。
// 通过观察易得：若c[i-1] ≤ 0，则c[i] := a[i]。
// 用e表示以i为结束的子数组的最大和以代替数组c，
// 则有：       e = max{ a[i], e + a[i] }
// ...
// 复杂度：O(n)

function __calMaxSubSumDP(arr) {
    if(arr.length === 0)
        return 0;
    
    let max_e = arr[0], max_res = max_e;
    let i = 1;
    while(i < arr.length) {
        // 计算c[i] = max{ a[i], c[i-1]+a[i] }
        max_e = (arr[i] > max_e + arr[i]? arr[i] : max_e + arr[i]);

        // 更新最终结果
        max_res = (max_e > max_res? max_e : max_res);

        // 指针右移
        i += 1;
    }

    return max_res;

}

function comp(data) {
    console.time('DIV')
    let res = __calMaxSubSumDiv(data, 0, data.length-1);
    console.log('DIV_res:', res);
    console.timeEnd('DIV');
    console.time('DP')
    let res = __calMaxSubSumDP(data);
    console.log('DP_res:', res);
    console.timeEnd('DP');
}


// test -------------------------------------------
let test_1 = {
    data: [364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575],
    cnt: 2519,
}
let data = [6,-3,-2,7,-15,1,2,2];

comp(data);