0053.最大子数组和

难度：🟡 中等

标签：数组、分治、动态规划

链接：53. 最大子数组和

题目描述

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

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

解题思路

核心思想

本题的目标是在一个整数数组中，找到一个和最大的连续子数组。这是一个经典的动态规划问题。核心思想是，当我们遍历到数组的第 i 个元素时，思考以这个元素结尾的子数组的最大和是多少。

思路选择

动态规划 (Kadane's Algorithm) 是解决此问题的标准最优思路。

• 我们可以定义 dp[i] 为以 nums[i] 这个元素结尾的连续子数组的最大和。

• 状态转移的关键在于：对于 dp[i]，我们只有两种选择：

  1. nums[i] 独自成为一个新的子数组。

  2. nums[i] 加入到以 nums[i-1] 结尾的最大和子数组中，形成一个更长的子数组。

• 因此，状态转移方程为：dp[i] = max(nums[i], dp[i-1] + nums[i])。

• 在计算 dp 数组的过程中，我们需要一个全局变量来记录所有 dp[i] 中的最大值，这个最大值就是最终的答案。

关键步骤

1. 初始化：初始化两个变量，globalMax 用于记录全局最大和，currentMax 用于记录以当前元素结尾的最大和。两者都初始化为数组的第一个元素 nums[0]。

2. 循环遍历：从第二个元素（索引 i = 1）开始遍历数组。

3. 状态转移：对于当前元素 nums[i]，更新 currentMax。currentMax 的新值是 nums[i] 本身与 currentMax + nums[i] 中的较大者。

4. 更新全局最大值：用更新后的 currentMax 来更新 globalMax，globalMax = Math.max(globalMax, currentMax)。

5. 返回结果：遍历结束后，globalMax 就是整个数组的最大子数组和。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    // dp[i] 表示以 nums[i] 结尾的最大子数组和
    let dp = [], maxValue = nums[0];
    dp[0] = nums[0];

    for (let i = 1; i < nums.length; i++) {
        // 状态转移方程正确
        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        // 实时更新全局最大值
        maxValue = Math.max(maxValue, dp[i]);
    }

    return maxValue;
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是数组 nums 的长度。我们只需要对数组进行一次完整的遍历。

• 空间复杂度：O(1) 推荐解法只使用了常数个额外变量，空间消耗是恒定的。

相关题目

• 0121.买卖股票的最佳时机

• 0152.乘积最大子数组

• 0056.合并区间

总结

本题是动态规划中的一个里程碑式的问题，其 O(1) 空间复杂度的解法（通常被称为“Kadane's 算法”）是面试中的高频考点。它完美地展示了如何通过状态压缩（用单个变量代替 DP 数组）来优化动态规划问题。