剑指 Offer 42. 连续子数组的最大和

[Geekhyt]

原题链接

状态定义

dp[i]：表示以 nums[i] 为结尾的连续子数组最大和。

状态转移方程

连续子数组则必须包含 nums[i]，否则不符合题意。

当 dp[i - 1] > 0 时，dp[i] = dp[i - 1] + nums[i]，当 dp[i - 1] <= 0 时，dp[i] = nums[i]。

所以状态转移方程为：

dp[i] = max(dp[i - 1] + nums[i], nums[i])

初始化

dp[0] = nums[0]，以 nums[0] 为结尾的连续子数组最大和为 nums[0]。

我们只需要关注前一个状态的值，不需要额外开辟一个数组空间记录，仅用两个变量即可。

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

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