53. 最大子数组和

题目链接：53. 最大子数组和

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

核心思考：为什么相向双指针会失效？

在处理连续区间求和问题时，直觉上容易引入滑动窗口或相向双指针策略。然而，针对本题的数据特征（存在负数），我们需要进行严密的逻辑验算以确定数据结构和算法模式的适用性。

相向双指针（从两端向内收缩）的有效性前提，是能够基于当前状态，明确且单调地排除某一侧的非优区间。但在存在负数的序列中，区间和失去了单调性。

致命缺陷验算：

1. 局部决策的不可判定性：例如 nums = [2, -100, 50, -100, 3]。即使两端起手都是正数，在向内收缩时，无法通过边界的局部大小比较，跨越深渊（-100）探测到被包裹在中间的全局最优解（50）。
2. 边界崩溃 (Edge Case)：如果采取“两边收紧跳过负数”的优化策略，面对全负数数组 nums = [-5, -2, -9]，寻找非负数的逻辑会导致指针直接越界，无法返回合法子数组。

结论：基于区间向内收缩的双指针在此场景完全失效。我们需要将架构视角切换为单向流式遍历。

解题思路：动态规划与状态转移 (Kadane 算法)

摒弃区间两端的动态维护，我们转而关注“前序状态”对“当前元素”的数值影响。

在 $O(n)$ 的单向遍历中，假设当前访问元素为 nums[i]，并维护一个变量 curr_sum 记录 nums[i] 之前的连续子数组累加和。对于是否将 nums[i] 纳入现有的连续区间，取决于严格的数学关系：

• 状态 A (curr_sum > 0)：curr_sum + nums[i] 必然大于单独的 nums[i]。前序状态提供了正向增益，应当继续累加。
• 状态 B (curr_sum < 0)：curr_sum + nums[i] 必然小于 nums[i] 本身。前序的累加和对当前连续区间产生了数值上的负向拖累。此时应当果断丢弃前序历史，直接以当前的 nums[i] 作为新子数组的起点（另起炉灶）。

全局最优的锁定与边界防范

由于 curr_sum 仅代表局部最优（以当前元素结尾的最大子数组和），它会随着数组元素的正负交替不断波动。因此，必须引入一个独立的状态变量 max_sum 来持续捕获并锁定历史峰值。

边界防范 (Edge Case)：
针对全负数数组的极限输入（如 [-5, -2, -9]），如果 max_sum 初始化为 0，则会漏算真实的负数最大值。因此，必须将其底层状态初始化为负无穷大 float('-inf')，以确保极值捕获的绝对鲁棒性。

代码实现 (Python)

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 全局峰值锁定，初始化为 -inf 防御全负数边界
        max_sum = float('-inf')
        # 局部连续和状态
        curr_sum = 0
        
        # O(N) 单向流式遍历
        for num in nums:
            # 状态转移：若前序累加和为负，则切断历史，消除负向拖累
            if curr_sum < 0:
                curr_sum = 0
                
            curr_sum = curr_sum + num
            
            # 动态更新全局最优解
            max_sum = max(curr_sum, max_sum)
            
        return max_sum

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 nums 的长度。我们只需要遍历一遍数组即可求得答案。
• 空间复杂度：$O(1)$，我们仅使用常数级别的空间来存放 curr_sum 和 max_sum 这两个变量。