53. 最大子数组和

LeetCode 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

提示

• 1lenums.lengthle105

• −104lenums[i]le104

---

解题思路与代码实现

核心思想

这道题是动态规划中的一个经典问题，最优雅的解法被称为“卡丹算法”（Kadane's Algorithm）。其核心思想是，当我们从左到右遍历数组时，对于每一个元素，我们都做出一个决策：是将当前元素加入到前面的子数组以延续它，还是从当前元素开始一个新的子数组。

决策的依据非常简单：如果前一个子数组的和为负数，那么它对于后续的求和只会起到“拖累”的作用。在这种情况下，我们不如抛弃它，直接从当前元素开始计算一个新的子数组和。

基于此，我们只需要维护两个变量：

1. currentMax：记录以当前元素为结尾的连续子数组的最大和。

2. globalMax：记录在整个遍历过程中所遇到的全局最大子数组和。

遍历完整个数组，globalMax 中存储的就是最终答案。

JavaScript 代码实现

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const maxSubArray = (nums) => {
    // globalMax 用于存储全局的最大子数组和。
    // 根据题目约束，子数组至少包含一个元素，因此可以安全地初始化为数组的第一个元素。
    let globalMax = nums[0];
    
    // currentMax 用于存储以当前元素结尾的连续子数组的最大和。
    let currentMax = nums[0];

    // 从第二个元素开始遍历数组
    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];
        
        // 核心决策：
        // 是将当前数字 num 加入之前的子数组（currentMax + num），
        // 还是从 num 本身开始一个新的子数组？
        // 我们选择两者中和更大的那个作为新的 currentMax。
        currentMax = Math.max(num, currentMax + num);
        
        // 在更新了以当前元素结尾的最大和之后，
        // 我们需要检查它是否也超过了已知的全局最大和。
        if (currentMax > globalMax) {
            globalMax = currentMax;
        }
    }

    return globalMax;
};

过程解析

我们用示例 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 来完整地走一遍这个过程：

索引 i	当前数字 num	currentMax (计算后)	globalMax (更新后)	决策备注
0	-2	-2 (初始化)	-2 (初始化)
1	1	max(1, -2 + 1) = 1	max(-2, 1) = 1	前面的和是负数，不如从 1 开始新数组。
2	-3	max(-3, 1 - 3) = -2	1	将 -3 加入，currentMax 变为 -2。
3	4	max(4, -2 + 4) = 4	max(1, 4) = 4	前面的和是负数，不如从 4 开始新数组。
4	-1	max(-1, 4 - 1) = 3	4	将 -1 加入，currentMax 变为 3。
5	2	max(2, 3 + 2) = 5	max(4, 5) = 5	将 2 加入，currentMax 变为 5。
6	1	max(1, 5 + 1) = 6	max(5, 6) = 6	将 1 加入，currentMax 变为 6，创下新高。
7	-5	max(-5, 6 - 5) = 1	6	将 -5 加入，currentMax 变为 1。
8	4	max(4, 1 + 4) = 5	6	将 4 加入，currentMax 变为 5。

循环结束，最终返回 globalMax 的值，即 6。

复杂度分析

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

• 空间复杂度： O(1)。我们只使用了 globalMax 和 currentMax 这两个额外的变量，没有使用随输入规模增长的额外空间。