数组题解——最大子数组和【LeetCode】
暴力法
这个方法在力扣平台上，提交运行后会超出时间限制
复杂度分析：
- 时间复杂度：O(N2)。
- 空间复杂度：O(1)。
class Solution:def maxSubArray(self, nums):"""找到 nums 数组中子数组的最大和:param nums: 数组:return: 最大子数组和"""size = len(nums)res = -float('inf') # 初始化为负无穷for i in range(size):sum_val = 0for j in range(i, size):sum_val += nums[j]res = max(res, sum_val)return res动态规划
算法的核心思想是 动态规划，通过状态压缩优化空间复杂度：
- 局部最大值（
sub_max）：- 表示以当前元素结尾的子数组的最大和。
- 如果前一个子数组的和
sub_max是正数，则对当前元素有正增益，可以继续累加。 - 如果前一个子数组的和
sub_max是负数，则对当前元素是负增益，应该抛弃前面的结果，从当前元素重新开始计算。
- 全局最大值（
max_sum）：- 记录遍历过程中所有局部最大值中的最大值。
- 每次更新局部最大值后，都会更新全局最大值。
算法运行过程
假设输入 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]，算法的运行过程如下：
遍历元素 (nums[i]) | sub_max 更新逻辑 | sub_max 值 | max_sum 值 |
|---|---|---|---|
| -2 | 初始化 | -2 | -2 |
| 1 | sub_max = -2（负增益，抛弃） | 1 | 1 |
| -3 | sub_max = 1（正增益，累加） | -2 | 1 |
| 4 | sub_max = -2（负增益，抛弃） | 4 | 4 |
| -1 | sub_max = 4（正增益，累加） | 3 | 4 |
| 2 | sub_max = 3（正增益，累加） | 5 | 5 |
| 1 | sub_max = 5（正增益，累加） | 6 | 6 |
| -5 | sub_max = 6（正增益，累加） | 1 | 6 |
| 4 | sub_max = 1（正增益，累加） | 5 | 6 |
最终结果为 6。
class Solution:def maxSubArray(self, nums):"""使用动态规划（状态压缩）找到 nums 数组中子数组的最大和:param nums: 数组:return: 最大子数组和"""if not nums: # 如果数组为空，返回 0return 0max_sum = nums[0] # 全局最大值，初始化为数组的第一个元素sub_max = nums[0] # 局部最大值，初始化为数组的第一个元素for i in range(1, len(nums)): # 从第二个元素开始遍历if sub_max > 0:# 前一个子组合最大值大于 0，正增益，继续累加sub_max += nums[i]else:# 前一个子组合最大值小于 0，负增益，抛弃前面的结果，从当前元素重新开始sub_max = nums[i]# 更新全局最大值max_sum = max(max_sum, sub_max)return max_sum # 返回全局最大值这两个 maxSubArray 实现都用于解决 最大子数组和 问题（即经典的「最大子段和」问题），但实现方式和效率有明显不同。
✅ 一、两种算法的本质区别
| 对比项 | 暴力解法 | 动态规划（Kadane 算法） |
|---|---|---|
| 核心思想 | 穷举所有可能的子数组，逐个求和并取最大值 | 当前状态仅与上一个状态有关，动态转移 |
| 实现方式 | 双重循环遍历所有子数组 | 单次遍历 + 局部最优推导全局最优 |
| 代码结构 | 两层 for 循环，维护当前子数组和 | 一层 for 循环，维护一个局部最大和 sub_max |
| 是否冗余 | 是，有大量重复计算 | 否，每个元素只处理一次 |
✅ 二、时间复杂度与空间复杂度对比
| 项目 | 暴力解法 | 动态规划（Kadane） |
|---|---|---|
| 时间复杂度 | O(n²) | O(n) |
| 空间复杂度 | O(1) | O(1) |
-
暴力解法：每个起点
i都遍历一遍后续的所有子数组结尾j，导致时间复杂度是平方级。 -
Kadane 算法：只需遍历一次数组，通过维护一个「以当前位置结尾的最大子数组和」，从而高效求解。
✅ 三、核心点解析
1. 暴力解法核心
-
穷举所有可能的子数组。
-
每次从下标
i开始，向后累计和，取最大值。 -
每个子数组和都要单独计算（冗余计算多）。
2. 动态规划核心（Kadane 算法）
-
状态定义：
sub_max[i]表示以i结尾的最大子数组和。 -
状态转移方程：
sub_max[i] = max(nums[i], sub_max[i - 1] + nums[i])直观理解为：当前元素是从头开始一个新的子数组，还是继续累加前面的子数组更优。
-
由于
sub_max[i]只依赖于sub_max[i-1]，因此可进行状态压缩为一个变量，降低空间复杂度。
✅ 四、使用场景与选择建议
| 场景 | 推荐算法 | 原因 |
|---|---|---|
| 学习暴力法、理解问题 | 暴力解法 | 帮助理解子数组枚举方式 |
| 实际开发、面试中高频 | 动态规划 | 快速、高效，时间复杂度低 |
✅ 总结
| 维度 | 暴力解法 | 动态规划（Kadane） |
|---|---|---|
| 时间复杂度 | O(n²) | O(n) |
| 空间复杂度 | O(1) | O(1) |
| 优点 | 易理解 | 高效、经典、面试常考 |
| 缺点 | 慢，无法处理大规模输入 | 初学者理解状态转移需一定抽象能力 |
👉 核心转化在于：从穷举所有可能，转为每一步只做一次决策，并记住最优解，避免重复计算。