题解 | #连续子数组的最大和(二)#

没看到typescript题解，我来补充一个，包含空间复杂度O(n),O(1)两种方法；

题解：直接在 连续数组最大和 题解结果中改造，增加left，right变量记录子数组左右序号即可，那么问题就转化成了，如何更新left，right变量。

export function FindGreatestSumOfSubArray(array: number[]): number {
    // write code here
    let maxVal = array[0];
    for(let i=1;i<array.length;i++) {
        if(array[i-1] > 0) {
            array[i] += array[i-1];
        }
        maxVal = maxVal < array[i] ? array[i] : maxVal;
    }
    return maxVal;
}

• 对于right，很明显当需要更新maxSumVal时就需要更新最大子数组的右边界，同时新增lastLeft记录当前left位置；
• 对于left，当resList[i-1] < 0 时，我们会重新计算子数组的连续和，因此这里也是更新left变量时机；
• 最后，根据left，right截取子数组空间时，要注意，按照我们的left，right更新方法，left可能会大于right，此时令left=lastLeft即可；

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型一维数组
 */
export function FindGreatestSumOfSubArray(array: number[]): number[] {
    // write code here
    let lastLeft = 0;
    let left = 0, right = 0;
    let maxVal = array[0];
    // ======================================================
    // 1.开辟新数组存储，空间复杂度O(n)
    // ======================================================
//     const resList = [array[0]];
//     for(let i=1;i<array.length;i++) {
//         if(resList[i-1] >= 0) {
//             resList[i] = resList[i-1] + array[i];
//         } else {
//             resList[i] = array[i];
//             left = i;
//         }
//         if(resList[i] >= maxVal) {
//             maxVal = resList[i];
//             right = i;
//         }
//     }
    // ======================================================
    // 2.无需开辟新数组，增加中间变量记录resList[i-1]即可
    // ======================================================
    let lastSumVal = array[0]
    for (let i=1;i<array.length;i++) {
        if(lastSumVal >= 0) {
            lastSumVal += array[i];
        } else {
            lastSumVal = array[i];
            left = i;
        }
        if(lastSumVal >= maxVal) {
            maxVal = lastSumVal;
            lastLeft = left;
            right = i;
        }
    }
    // ======================================================
    if(right < left) {
        left = lastLeft;
    }
    return array.splice(left, right-left+1)
}