问题说明（含有示例）

问题描述：给定一个整数数组 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解释：连续子数组 [5,4,-1,7,8] 的和最大，为 23。

解题关键

• 状态定义：

  • current_max：表示 “以当前元素结尾的最大连续子数组和”。
  • global_max：表示遍历过程中出现的最大子数组和（最终答案）。

• 核心逻辑：

  • 初始化：current_max 和 global_max 均设为数组第一个元素（确保子数组至少包含一个元素）。
  • 遍历数组从第二个元素开始，对每个元素 num：
    • 更新 current_max：选择 “将 num 加入之前的子数组”（current_max + num）或 “从 num 重新开始子数组”（num），取两者最大值（current_max = max(num, current_max + num)）。
    • 更新 global_max：若 current_max 超过 global_max，则更新 global_max。

• 复杂度：

  • 时间复杂度：O(n)（仅遍历数组一次）。
  • 空间复杂度：O(1)（仅用有限变量存储中间结果）。

对应代码：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        current_max = global_max = nums[0]
        for num in nums[1:]:
            current_max = max(num, current_max + num)
            # 每次更新current_max后，立即检查并更新global_max
            if current_max > global_max:
                global_max = current_max
        return global_max

基础知识

1. 多变量赋值代码中 current_max = global_max = nums[0] 是 Python 的多变量同时赋值语法，等价于：

   python

   运行

   current_max = nums[0]
   global_max = nums[0]
   

   作用：简洁地初始化两个变量，避免重复代码。

2. 列表切片（List Slicing）for num in nums[1:] 中，nums[1:] 表示截取数组 nums 从索引 1（第二个元素）到末尾的子数组。例如：nums = [1,2,3] 时，nums[1:] 结果为 [2,3]。作用：控制遍历范围，从第二个元素开始处理，避免重复处理初始化时已用到的第一个元素。

3. for 循环遍历for num in nums[1:] 是 Python 的迭代遍历方式，直接迭代数组元素，无需通过索引访问。优势：代码更简洁，避免索引越界错误，可读性更高。

4. 内置函数 max()核心逻辑 current_max = max(num, current_max + num) 中，max() 用于取两个值中的较大者。作用：快速判断 “延续之前的子数组” 和 “重新开始子数组” 哪种选择更优，替代冗长的 if-else 逻辑。

5. 函数定义与类型注解函数定义 def maxSubArray(self, nums: List[int]) -> int: 中：

   • def 是函数定义关键字，self 表示该函数是类的实例方法。
   • 类型注解 nums: List[int] 和 -> int 分别提示参数 nums 是整数列表、返回值是整数（仅起提示作用，不强制类型检查）。

进阶知识

该问题的解决还涉及算法设计与优化的进阶思想：

1. 动态规划的空间优化标准动态规划需定义数组 dp[i] 存储 “以第 i 个元素结尾的最大子数组和”，空间复杂度为 O(n)。优化：由于 dp[i] 仅依赖前一个值 dp[i-1]，可用变量 current_max 替代数组，将空间复杂度降至 O(1)。

2. 贪心算法思想算法通过 “每一步选择局部最优解”（即对当前元素选择能得到更大和的子数组延续方式），最终得到全局最优解。合理性：连续子数组的特性决定了 “局部最优选择” 必然包含在全局最优解中（数学上可证明 Kadane 算法的正确性）。

3. 边界情况处理算法无需额外判断边界，通过初始化逻辑自然覆盖所有场景：

   • 数组长度为 1 时：循环不执行，直接返回初始化的 global_max（即唯一元素）。
   • 数组全为负数时：current_max 会选择最大的负数（局部最优），global_max 最终记录该值（满足 “子数组至少含一个元素” 的要求）。

4. 复杂度分析

   • 时间复杂度 O(n)：仅遍历数组一次，每次循环内的操作（max()、赋值）均为常数时间。
   • 空间复杂度 O(1)：仅使用 current_max、global_max 等固定数量的变量，空间消耗与数组长度无关。该复杂度确保算法可高效处理大规模数据（如长度为 10^5 的数组）。