#53

中等

高频

动态规划

最大子数组和

这是一道围绕数组、分治、动态规划展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

数组

分治

动态规划

原题练习

题目分析

给你一个整数数组，要求找出和最大的连续子数组，并返回这个最大和。

注意这里强调的是“连续”，不能跳着选。

比如 [-2,1,-3,4,-1,2,1,-5,4] 里，最大和对应的连续子数组是 [4,-1,2,1]，答案是 6。

一句话概括：

在所有连续子数组里，找出和最大的那一段。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：把状态定义成“以当前位置结尾的最大子数组和”，每次只判断是续上前面还是从当前元素重开。

结构化讲解

面试时怎么讲

开场思路

这题我会用线性 DP。关键是把状态定义成“以当前位置结尾的最大子数组和”。

核心过程

设 current 表示当前位置结尾的最优和。
走到新元素时，只比较两种情况：从当前元素重新开始，或者把它接到前面的连续子数组后面。
然后用 current 去更新全局答案 answer。
整个数组只需要从左到右扫描一次。

复杂度总结

时间复杂度 O(n)，空间复杂度 O(1)。

面试补一句：这题最值钱的收获不是答案本身，而是学会怎么定义线性 DP 状态。

核心思路

这题最核心的不是动态规划三个字，而是状态定义。只要把 current 定义成“必须以当前位置结尾”的最优值，转移就会变得非常直接。

步骤讲解

定义当前位置结尾的状态

用 current 表示“以 nums[i] 结尾的最大连续子数组和”。

为什么这样做：这个定义天然满足连续性要求，也能把决策压缩成当前位置的一次选择。

对应代码提示：int current = nums[0];

决定是重开还是接上前面

走到 nums[i] 时，只比较 nums[i] 和 current + nums[i] 哪个更大。

为什么这样做：当前位置结尾的最优解，要么单独从当前元素开始，要么承接之前的连续区间。

对应代码提示：current = Math.max(nums[i], current + nums[i]);

实时维护全局最优答案

每次更新完 current 后，再用它刷新全局最大值 answer。

为什么这样做：任何一个位置结尾的最优解，都有可能成为最终答案。

对应代码提示：answer = Math.max(answer, current);

从左到右扫描一遍数组

从第二个元素开始，按同样规则持续更新状态和答案。

为什么这样做：状态只依赖前一个位置，因此整个过程可以线性完成。

对应代码提示：for (int i = 1; i < nums.length; i++) { ... }

易错点

把题目理解成任选若干元素

最大子数组和要求的是连续子数组，不能跳着选正数。

正确理解：状态必须带上“以当前位置结尾”这个连续约束。

忽略全负数场景

如果把初始答案设成 0，全负数数组会被错误处理成 0。

正确理解：current 和 answer 都应该从 nums[0] 初始化。

只更新 current，不更新全局答案

当前位置最优值只是局部状态，最终答案还需要单独维护。

正确理解：每次计算完 current 后，都立即执行 answer = Math.max(answer, current)。

复杂度与适用判断

时间复杂度：O(n)

空间复杂度：O(1)

比其他方案更好在哪里：比分治法更直接，时间复杂度也更优，适合作为默认主解法。

代价是什么：理论表达上没有分治法那么“结构化”，但工程上更实用。

适用判断：当题目涉及连续区间最优解，且当前位置状态只依赖前一个状态时，优先考虑线性 DP。

额外提醒

“以当前位置结尾”是这题最关键的状态定义。
前缀和一旦是负贡献，就没有继续保留的价值。

其他语言 / 其他解法

分治算法

分治法从结构上把问题拆成左半、右半和跨中点三部分。它更适合讲清“最大子数组为什么可以递归分解”，但不是这题最优主解。

时间复杂度：O(n log n)

空间复杂度：O(log n)

一句话思路：把数组拆成左右两半，分别求解后，再计算横跨中点的最大子数组和做合并。

class Solution {
    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r) {
            return new Status(a[l], a[l], a[l], a[l]);
        }
        int m = (l + r) >> 1;
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    public Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }
}

动画演示

如果你还没完全看懂，可以展开动画演示。

动态规划动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

整数数组:

准备就绪 - 输入整数数组，然后点击开始