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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param array int整型一维数组
 * @return int整型一维数组
 */
function FindGreatestSumOfSubArray(array) {
    // 动态规划：状态转移数组dp[i]表示以下标i为终点的最大连续子数组和
    // dp[i] = max(dp[i - 1] + array[i], dp[i])
    // dp[i]只有两个方向可以推出来：
    // dp[i - 1] + array[i]，即：array[i]加入当前连续子序列和
    // array[i]，即：从头开始计算当前连续子序列和
    let dp = [];
    dp[0] = array[0];
    let max = dp[0];
    // 记录每次连续子数组的首尾索引
    let start = 0;
    let end = 0;
    // 记录最大且区间最长的连续子数组的首尾索引
    let maxStart = 0;
    let maxEnd = 0;
    for (let i = 1; i < array.length; i++) {
        end++;
        // 状态转移
        dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
        // 更新区间新起点
        if (dp[i - 1] + array[i] < array[i]) {
            start = end;
        }
        if (dp[i] > max || (dp[i] === max && (end - start) > (maxEnd - maxStart))) {
            maxStart = start;
            maxEnd = end;
            max = dp[i];
        }
    }
    let res = [];
    for (let i = maxStart; i <= maxEnd; i++) {
        res.push(array[i]);
    }
    return res;
}
module.exports = {
    FindGreatestSumOfSubArray: FindGreatestSumOfSubArray,
};