53. 最大子数组和

题目链接（中等）

题目描述

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

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

数据范围：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

进阶：如果你已经实现复杂度为 $O(n)$ 的解法，尝试使用更为精妙的 分治法 求解。

示例

示例 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

方法一：动态规划

思路及解法

设 dp(i) 为以第 i 个数结尾的连续子数组的最大和。对于 nums[i]，有两种选择：

1. 单独成为一段：dp(i) = nums[i]；
2. 接在 dp(i-1) 后面：dp(i) = dp(i-1) + nums[i]。

取两者较大值，得到转移方程：

$$dp(i) = \max\{dp(i-1) + nums[i],\ nums[i]\}$$

直觉理解：如果以 nums[i-1] 结尾的那段和是正的，它对 nums[i] 有增益，就接上；如果是负的，接上反而拖累，不如从 nums[i] 重新开始。

答案是所有 dp(i) 中的最大值（注意不是 dp(n-1)，因为最大子数组不一定以最后一个数结尾）。

因为 dp(i) 只和 dp(i-1) 有关，可以用一个变量滚动维护，无需数组，空间降到 $O(1)$。

代码

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        pre = 0
        ans = nums[0]
        for x in nums:
            pre = max(pre + x, x)
            ans = max(ans, pre)
        return ans

复杂度分析

• 时间复杂度：$O(n)$，只需遍历数组一次。
• 空间复杂度：$O(1)$，只使用常数个变量。

方法二：前缀和重置视角

思路及解法

与方法一等价，只是写法不同：用一个变量 cur 累计当前子数组的和，若 cur 变成负数，说明它对后面没有贡献，直接清零重新开始。

代码

n = int(input())
a = [int(x) for x in input().split()]

cur = 0
ans = float('-inf')
for i in range(n):
    cur += a[i]
    ans = max(ans, cur)  
    if cur < 0:
        cur = 0        
print(ans)

方法三：分治

思路及解法

分治法把区间 [l, r] 从中间 m 切开，递归求解左右子区间 [l, m] 和 [m+1, r]，再把结果合并。

关键：维护四个量

变量	含义
lSum	[l, r] 内以 l 为左端点的最大子段和
rSum	[l, r] 内以 r 为右端点的最大子段和
mSum	[l, r] 内的最大子段和
iSum	[l, r] 的区间和

对于长度为 1 的区间 [i, i]，四个量都等于 nums[i]。

合并规则：设左子区间为 L，右子区间为 R，则：

• iSum = L.iSum + R.iSum；
• lSum = max(L.lSum, L.iSum + R.lSum)：要么完全在左子区间，要么左子区间全取 + 右子区间从左端开始的一段；
• rSum = max(R.rSum, R.iSum + L.rSum)：对称；
• mSum = max(L.mSum, R.mSum, L.rSum + R.lSum)：最大子段要么在左子区间、要么在右子区间、要么跨越中点（左子区间右端一段 + 右子区间左端一段）。

递归到区间长度为 1 时返回，逐层合并，最终 get(0, n-1).mSum 就是答案。

代码

class Status:
    """表示一个区间的四个关键信息"""
    __slots__ = ('l_sum', 'r_sum', 'm_sum', 'i_sum')

    def __init__(self, l_sum: int, r_sum: int, m_sum: int, i_sum: int):
        self.l_sum = l_sum   # 以区间左端点为起点的最大子段和
        self.r_sum = r_sum   # 以区间右端点为终点的最大子段和
        self.m_sum = m_sum   # 区间内的最大子段和
        self.i_sum = i_sum   # 区间总和


class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        def push_up(L: Status, R: Status) -> Status:
            """合并左右子区间的信息，得到父区间的信息"""
            i_sum = L.i_sum + R.i_sum
            l_sum = max(L.l_sum, L.i_sum + R.l_sum)
            r_sum = max(R.r_sum, R.i_sum + L.r_sum)
            m_sum = max(L.m_sum, R.m_sum, L.r_sum + R.l_sum)
            return Status(l_sum, r_sum, m_sum, i_sum)

        def get(l: int, r: int) -> Status:
            """递归求解区间 [l, r] 的 Status"""
            if l == r:
                v = nums[l]
                return Status(v, v, v, v)
            m = (l + r) // 2
            L = get(l, m)
            R = get(m + 1, r)
            return push_up(L, R)

        return get(0, len(nums) - 1).m_sum

复杂度分析

• 时间复杂度：$O(n)$。递归树的每个节点都只做常数次合并，总节点数为 $O(n)$。
• 空间复杂度：$O(\log n)$。递归栈深度为 $O(\log n)$。

三种方法对比

方法	时间	空间	是否易理解	特点
动态规划	$O(n)$	$O(1)$	容易	代码极短，最优解法
前缀和重置	$O(n)$	$O(1)$	容易	与 DP 等价，写法不同
分治	$O(n)$	$O(\log n)$	较难	可扩展为线段树，支持区间查询与修改

为什么还要学分治？

分治解法本身在本题中不如动态规划，但它可以扩展成线段树：把所有子区间的信息建树保存后，可以在 $O(\log n)$ 时间内查询任意区间的最大子段和，也可以修改数组中的值后仍保持 $O(\log n)$ 查询。面对大规模查询场景时，这种结构优势明显。

总结

• 动态规划：核心转移方程 dp(i) = max(dp(i-1) + nums[i], nums[i])，用滚动变量实现 $O(n)$ 时间、$O(1)$ 空间，面试首选；
• 前缀和重置：与 DP 等价，注意先更新 ans 再清零 cur；
• 分治：维护 lSum / rSum / mSum / iSum 四个量，合并时注意跨越中点的情况，是线段树区间合并的入门模型；
• 本题推荐掌握动态规划，分治作为进阶了解即可。