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

易错分析

DP数组定义的是以当前位置arr[i]结尾时的所有连续子数组的最大和，因为是连续数字的数组，所以增加arr[i]后这个arr[i]必须保证在连续子数组中，所以更新的dp[i]应该要包含arr[i]才能保证arr[i]和前面的数字连续，如果更新中包含了dp[i-1]，当前位置i结尾的所有连续子数组的最大和可能就是dp[i-1]，此时arr[i]就不连续了。

function FindGreatestSumOfSubArray(array)
{
    // write code here
    const dp = new Array(array.length).fill(-Infinity);
    dp[0] = arr[0];

    for (let i = 1; i < array.length; ++i) {
        // dp[i] = Math.max(dp[i-1], arr[i], arr[i]+dp[i-1]);
        dp[i] = Math.max(array[i], array[i]+dp[i-1]);  // dp[i-1]存放的已经是以i-1为结尾的所有子数组的最大和，所以只需考虑增加arr[i]后是否会使这个最大和变化
    }

    return Math.max(...dp);
}
module.exports = {
    FindGreatestSumOfSubArray : FindGreatestSumOfSubArray
};

优化

直接用array充当dp数组，因为从底向上递推，上面的情况只需要下面整合好的信息。

function FindGreatestSumOfSubArray(array)
{
    // write code here
    // const dp = new Array(array.length).fill(-Infinity);
    // dp[0] = array[0];

    for (let i = 1; i < array.length; ++i) {
        array[i] = Math.max(array[i], array[i]+array[i-1]);
    }

    return Math.max(...array);
}
module.exports = {
    FindGreatestSumOfSubArray : FindGreatestSumOfSubArray
};