最大子数组和

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：动态规划、分治法

给你一个整数数组 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

2. 解题思路拆解

方法：动态规划 (Kadane's Algorithm)

这是一个经典的动态规划问题。我们需要找到一个连续子数组，使得它的和最大。

定义状态：
- 定义 dp[i] 为：以 nums[i] 结尾的连续子数组的最大和。
- 注意：这里强调必须以 nums[i] 结尾，这样才能保证子数组的连续性。
状态转移方程：
- 对于 nums[i]，它有两种选择：
  1. 加入前面的子数组：如果前面的子数组和 dp[i-1] 是正数，那么加上它肯定比自己单干强。此时 dp[i] = nums[i] + dp[i-1]。
  2. 自己另起炉灶：如果前面的子数组和 dp[i-1] 是负数，加上它只会拖累自己，不如自己重新开始。此时 dp[i] = nums[i]。
- 综上，转移方程为：dp[i] = Math.max(nums[i], nums[i] + dp[i-1])。
最终答案：
- 题目要求的答案是全局最大和，不一定非要以最后一个元素结尾。所以我们要遍历所有的 dp[i]，找到其中的最大值。
空间优化：
- 我们发现 dp[i] 只依赖于 dp[i-1]。因此，我们不需要维护一个完整的 dp 数组，只需要用一个变量 pre 来记录“前一个位置的最大子数组和”即可。

3. 代码实现

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let pre = 0; // 记录 dp[i-1]
    let maxAns = nums[0]; // 记录全局最大值
    
    for (const x of nums) {
        // 状态转移：dp[i] = max(dp[i-1] + x, x)
        // 如果 pre > 0，则 pre + x > x，保留 pre；否则丢弃 pre，从 x 重新开始
        pre = Math.max(pre + x, x);
        
        // 更新全局最大值
        maxAns = Math.max(maxAns, pre);
    }
    
    return maxAns;
};

代码执行演示

输入 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

初始化：pre = 0, maxAns = -2 (或者取第一个元素)
x = -2：pre = max(0-2, -2) = -2。maxAns = -2。
x = 1：pre = max(-2+1, 1) = 1。maxAns = 1。 (丢弃了之前的 -2，从 1 重新开始)
x = -3：pre = max(1-3, -3) = -2。maxAns = 1。
x = 4：pre = max(-2+4, 4) = 4。maxAns = 4。 (丢弃之前的负和，从 4 开始)
x = -1：pre = max(4-1, -1) = 3。maxAns = 4。
x = 2：pre = max(3+2, 2) = 5。maxAns = 5。
x = 1：pre = max(5+1, 1) = 6。maxAns = 6。 (找到最大和 6)
x = -5：pre = max(6-5, -5) = 1。maxAns = 6。
x = 4：pre = max(1+4, 4) = 5。maxAns = 6。

最终返回 6。

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。只需要遍历一次数组。
空间复杂度	$O(1)$。只需要常数个变量。

最大子数组和 ​

1. 题目呈现 ​

2. 解题思路拆解 ​

方法：动态规划 (Kadane's Algorithm) ​

3. 代码实现 ​

代码执行演示 ​