最大子数组和 图解题解

最大子数组和这道题在问什么

给一个整数数组 nums（有正有负），找一个连续的子数组，至少包含一个元素，使它的元素和最大，返回这个和。「连续」是全部难度的来源：如果允许任选元素，把正数全挑出来就完了；正因为必须连成一片，才会出现「要不要为了后面的大正数，忍着带上中间几个负数」这种权衡。

为什么暴力枚举是 O(n²)，慢在哪

暴力做法是枚举子数组的起点和终点，配合前缀和可以把每段的和算到 O(1)，但起终点组合仍有约 n²/2 种，整体 O(n²)。慢的根源是重复权衡：以位置 i 结尾的各段和，与以 i+1 结尾的各段和之间只差一个元素，暴力却把它们当成不相干的问题从头算。如果「以 i 结尾的最优」能一步递推出「以 i+1 结尾的最优」，整个问题就只剩一趟线性扫描。

状态为什么要定义成「必须以第 i 个数结尾」

直接定义「前 i 个数里的最大子数组和」是递推不动的：那个最优段可能结束在前面任何位置，跟第 i+1 个数接不接得上说不清，新元素来了无从更新。加一个限制就通了——定义 dp[i] 为「所有以第 i 个数结尾的子数组」里的最大和。锚死了结尾，第 i+1 个数的处境立刻清晰：它要么接在前一段屁股后面，要么自己另起一段，只有这两种可能。

这个定义不会漏掉答案：任何子数组总得在某个位置结尾，把每个位置结尾的最优都算出来，全局最大值就藏在其中。所以最终答案是所有 dp[i] 里的最大值，而不是最后一个 dp——最优段完全可能在数组中间就结束了，示例 [-2,1,-3,4,-1,2,1,-5,4] 的答案 6 对应中段的 [4,-1,2,1]，就不在末尾。

前面的和为负就丢掉，为什么是对的

转移写出来是 dp[i] = max(nums[i], dp[i-1] + nums[i])，白话就是「接上前段」与「另起炉灶」二选一。它的正确性一句话可以点透：前段能提供的全部价值就是它的和 dp[i-1]——这个和是正数，接上等于白赚一笔垫底分；是负数，接上只会把自己拖低，还不如从 nums[i] 从零开始。注意被丢弃的判据是「前段的和为负」，不是「前面出现过负数」：示例里 4 后面跟着 -1，因为当时累计和 4 - 1 = 3 仍是正的，继续带着走才吃到了后面的 2 和 1。

由于 dp[i] 只依赖 dp[i-1]，连数组都不用开，两个变量就够：cur 滚动记「以当前数结尾的最大和」，best 记全程最大值。这就是 Kadane 算法的全部。

复杂度与最容易踩的边界

时间 O(n)：数组只扫一遍，每步一次比较一次加法。空间 O(1)：只有 cur、best 两个变量。

最经典的坑是 best 的初值：必须设成 nums[0]，不能设 0。数组全是负数时，正确答案是其中最大的那个负数，初值 0 会让你错误地返回 0——而空子数组是不允许的，题目要求至少含一个元素。另一个坑前面已提：答案是扫描全程的最大值，别返回最后一步的 cur。

Python

def maxSubArray(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)   # 另起 or 接上
        best = max(best, cur)
    return best

C++

int maxSubArray(vector<int>& nums){
    int cur = nums[0], best = nums[0];
    for(int i = 1; i < nums.size(); i++){
        cur = max(nums[i], cur + nums[i]);
        best = max(best, cur);
    }
    return best;
}

Java

int maxSubArray(int[] nums){
    int cur = nums[0], best = nums[0];
    for(int i = 1; i < nums.length; i++){
        cur = Math.max(nums[i], cur + nums[i]);
        best = Math.max(best, cur);
    }
    return best;
}