53. 最大子序和

[Geekhyt]

原题链接

动态规划

遍历数组，以当前遍历到的每一个点为终点来计算当前子序列的最大和，每一个点的结果都是基于前一个点的最大子序列和计算得出的。

状态转移方程

res[i] = Math.max(res[i - 1] + cur[i], cur[i])

• cur: 当前最大连续子序和
• res: 最终结果

const maxSubArray = function(nums) {
    const len = nums.length
    const dp = new Array(len).fill(1)
    dp[0] = nums[0]
    let res = dp[0]
    for (let i = 1; i < len; i++) {
        if (dp[i - 1] > 0) {
            dp[i] = dp[i - 1] + nums[i]
        } else {
            dp[i] = nums[i]
        }
        res = Math.max(res, dp[i])
    }
    return res
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)

状态压缩

每一个点的结果只和前一个点有关，我们仅用一个变量来维护即可，可以将空间复杂度降低到 O(1)。

对数组进行遍历，如果 cur 大于 0，则 cur 加上当前遍历的数字 num。

否则 cur 只会对当前结果起到负作用，并不是我们想要的，需要舍弃，更新当前遍历数字 num 为 cur。

每次遍历最后需要比较 res 和 cur 的大小，将最大值给到 res。

遍历结束后返回结果。

const maxSubArray = function(nums) {
    let res = nums[0]
    let cur = 0
    for (const num of nums) {
        if (cur > 0) {
            cur += num
        } else {
            cur = num
        }
        res = Math.max(res, cur)
    }
    return res
}

• 时间复杂度: O(n)
• 空间复杂度: O(1)