数组题解——最大子数组和​【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 = 0
              for j in range(i, size):
                  sum_val += nums[j]
                  res = max(res, sum_val)
          return res

  动态规划

  算法的核心思想是 动态规划，通过状态压缩优化空间复杂度：

  1. 局部最大值（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:  # 如果数组为空，返回 0
              return 0
          max_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)
        优点	易理解	高效、经典、面试常考
        缺点	慢，无法处理大规模输入	初学者理解状态转移需一定抽象能力

        👉 核心转化在于：从穷举所有可能，转为每一步只做一次决策，并记住最优解，避免重复计算。

        
        （图片来源网络，侵删）
        
        （图片来源网络，侵删）