最大子数组和

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

简单做法：以每个元素开头获取后续所有子数组，找到和最大的那个子数组，然后找下一个元素开头的最大子数组，取所有最大子数组中最大的那个子数组，时间复杂度O（n^2）

进阶做法： 要解决最大子数组和问题，最经典且高效的方法是Kadane算法（动态规划思想），时间复杂度为O(n)，空间复杂度为O(1)。该方法通过遍历数组，动态维护“当前最大子数组和”，避免了暴力枚举的高复杂度。

方法思路

核心逻辑：对于数组中的每个元素，判断“将其加入当前子数组”还是“以其为起点重新开始子数组”，取两者中的最大值作为新的“当前最大子数组和”，并实时更新全局最大和。

1. 初始化变量：

   • currentMax：记录以当前元素为结尾的最大子数组和（初始值为数组第一个元素）。
   • globalMax：记录全局最大子数组和（初始值为数组第一个元素）。

2. 遍历数组：
   从第二个元素开始，对于每个元素 nums[i]：

   • currentMax = max(nums[i], currentMax + nums[i])（选择继续当前子数组或重新开始）。
   • globalMax = max(globalMax, currentMax)（更新全局最大值）。

代码实现

function maxSubArray(nums) {
    if (nums.length === 0) return 0;
    
    let currentMax = nums[0];
    let globalMax = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        // 选择：以当前元素为起点，或加入之前的子数组
        currentMax = Math.max(nums[i], currentMax + nums[i]);
        // 更新全局最大和
        globalMax = Math.max(globalMax, currentMax);
    }
    
    return globalMax;
}

示例分析

以数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例：

步骤	当前元素	currentMax（当前子数组和）	globalMax（全局最大和）
初始	-2	-2	-2
i=1	1	max(1, -2+1)=1	max(-2, 1)=1
i=2	-3	max(-3, 1-3)=-2	max(1, -2)=1
i=3	4	max(4, -2+4)=4	max(1, 4)=4
i=4	-1	max(-1, 4-1)=3	max(4, 3)=4
i=5	2	max(2, 3+2)=5	max(4, 5)=5
i=6	1	max(1, 5+1)=6	max(5, 6)=6
i=7	-5	max(-5, 6-5)=1	max(6, 1)=6
i=8	4	max(4, 1+4)=5	max(6, 5)=6

最终结果为 6（对应子数组 [4, -1, 2, 1]）。

与暴力解法的对比

• 暴力解法：枚举所有可能的子数组（O(n²) 种），计算每个子数组的和（O(n)），总时间复杂度 O(n³)，效率极低。
• Kadane算法：仅需一次遍历（O(n)），每个元素仅被处理一次，时间复杂度 O(n)，空间复杂度 O(1)，是最优解法。

特殊情况处理

• 数组全为负数：返回最大的单个元素（如 [-3, -1, -2] 返回 -1）。
• 数组长度为1：直接返回该元素。

总结

Kadane算法通过动态规划的思想，避免了重复计算子数组和，高效地找到最大连续子数组和。其核心是“贪心选择”：对于每个元素，只关心“是否延续之前的子数组”，从而将问题简化为线性遍历。这种方法远优于暴力枚举，是解决该问题的标准解法。

Kadane算法

Kadane算法是一种用于求解最大子数组和问题的高效算法，由计算机科学家Jay Kadane提出。它通过动态规划（或贪心）思想，在O(n) 时间复杂度内完成求解，是该问题的最优解法。

核心问题：最大子数组和

给定一个整数数组 nums，找到其中连续子数组（至少包含一个元素）的最大和。例如：

• 输入 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]，输出 6（对应子数组 [4, -1, 2, 1]）。
• 输入 nums = [5, 4, -1, 7, 8]，输出 23（对应子数组 [5,4,-1,7,8]）。

Kadane算法的核心思想

对于数组中的每个元素 nums[i]，考虑两种选择：

1. 将 nums[i] 加入之前的子数组（延续当前子数组）；
2. 以 nums[i] 为起点，重新开始一个新的子数组。

取两种选择中的最大值，作为“以 nums[i] 为结尾的最大子数组和”，并实时更新全局的最大和。

算法步骤

1. 初始化变量：

   • current_max：记录“以当前元素为结尾的最大子数组和”（初始值为 nums[0]）。
   • global_max：记录全局的最大子数组和（初始值为 nums[0]）。

2. 遍历数组（从第二个元素开始）：
   对于每个元素 nums[i]：

   • 更新 current_max：current_max = max(nums[i], current_max + nums[i])
     （含义：要么以 nums[i] 为起点，要么延续之前的子数组）。
   • 更新 global_max：global_max = max(global_max, current_max)
     （含义：用当前的最大子数组和刷新全局最大值）。

3. 返回结果：遍历结束后，global_max 即为最大子数组和。

示例演示

以 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例，步骤如下：

索引 i	nums[i]	current_max（当前结尾的最大和）	global_max（全局最大和）
0	-2	-2（初始值）	-2（初始值）
1	1	max(1, -2 + 1) = 1	max(-2, 1) = 1
2	-3	max(-3, 1 + (-3)) = -2	max(1, -2) = 1
3	4	max(4, -2 + 4) = 4	max(1, 4) = 4
4	-1	max(-1, 4 + (-1)) = 3	max(4, 3) = 4
5	2	max(2, 3 + 2) = 5	max(4, 5) = 5
6	1	max(1, 5 + 1) = 6	max(5, 6) = 6
7	-5	max(-5, 6 + (-5)) = 1	max(6, 1) = 6
8	4	max(4, 1 + 4) = 5	max(6, 5) = 6

最终结果为 6，对应子数组 [4, -1, 2, 1]。

算法原理（动态规划视角）

Kadane算法可视为动态规划的简化：

• 定义 dp[i] 为“以 nums[i] 结尾的最大子数组和”。
• 状态转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])
  （解释：若 dp[i-1] 为正，延续子数组更优；否则，以 nums[i] 为起点更优）。
• 全局最大和为 max(dp[0], dp[1], ..., dp[n-1])。

由于 dp[i] 仅依赖 dp[i-1]，可省去数组存储，用变量 current_max 替代，空间复杂度优化为 O(1)。

特殊情况处理

1. 数组全为负数：例如 nums = [-5, -3, -2]，此时最大子数组为单个最大元素（-2）。Kadane算法会自动处理（每次 current_max 取最大的单个元素）。
2. 数组长度为1：直接返回该元素（如 nums = [5] 返回 5）。
3. 允许空数组：若题目允许子数组为空（最大和为0），需在最后判断 global_max 是否为负，若为负则返回0（需根据具体题目调整）。

与其他方法对比

方法	时间复杂度	空间复杂度	特点
暴力枚举	O(n²)	O(1)	枚举所有子数组，效率低
分治法	O(n log n)	O(log n)	递归拆分问题，较复杂
Kadane算法	O(n)	O(1)	线性遍历，高效简洁

Kadane算法是最优解，尤其适合大规模数组（如n=10⁵时，暴力法完全不可行）。

应用场景

• 最大子数组和问题（经典场景）。
• 衍生问题：最大子矩阵和（可转化为一维问题后应用Kadane算法）、最大子序列和（非连续，需调整逻辑）等。

总结

Kadane算法的核心是**“贪心选择”**：对每个元素，仅关注“是否延续之前的子数组”，通过一次遍历即可找到全局最优解。其简洁性和高效性使其成为解决最大连续子数组问题的标准方法，也是动态规划思想的经典应用。