53. 最大子数组和

Origin: LeetCode 53

题目描述

给定一个整数数组 nums，找出具有最大和的连续子数组（至少包含一个元素），返回其最大和。

示例

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6 Explanation: 连续子数组 [4, -1, 2, 1] 的和最大，为 6。

Input: nums = [1] Output: 1

Input: nums = [5, 4, -1, 7, 8] Output: 23

约束

• 1 <= nums.length <= 10
• -10^4 <= nums[i] <= 10

关键信息

• 连续子数组（不是子序列）
• 至少包含一个元素
• DP：dp[i] = max(nums[i], dp[i-1] + nums[i])
• 可优化为 O(1) 空间

Resolution

我的解法（滚动变量 O(1) 空间）

function maxSubArray(nums: number[]): number {
    let pre = nums[0]
    let max = nums[0]
    for (let i = 1; i < n; i++) {
        pre = Math.max(pre + nums[i], nums[i])
        max = Math.max(pre, max)
    }
    return max
}

数组版（O(n) 空间，第一版）

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

解题思路

dp[i] = max(nums[i], dp[i-1] + nums[i])。要么从当前元素重新开始，要么接着前面的和。

滚动变量优化：不需要数组，只用 pre 记录前一个状态，max 记录全局最大值。

踩坑

• 返回值不是 dp[n-1]，最大和可能出现在中间，要返回 Math.max(…dp) 或滚动维护 max
• DP 方程不是 max(dp[i-1]+nums[i], dp[i-1])（子序列思路），是 max(nums[i], dp[i-1]+nums[i])（连续子数组）

复杂度

• 时间：O(n)
• 空间：O(1)，滚动变量