题目链接 · 灵神原题解（署名来源）

方法一：前缀和 + 贪心

前置知识：前缀和

由于子数组的元素和等于两个前缀和的差，所以求出 $\mathit{\text{nums}}$ 的前缀和，问题就变成 121. 买卖股票的最佳时机 了。本题子数组不能为空，相当于一定要交易一次。

我们可以一边遍历数组计算前缀和，一边维护前缀和的最小值（相当于股票最低价格），用当前的前缀和（卖出价格）减去前缀和的最小值（买入价格），就得到了以当前元素结尾的子数组和的最大值（利润），用它来更新答案的最大值（最大利润）。

请注意，由于题目要求子数组不能为空，应当先计算前缀和-最小前缀和，再更新最小前缀和。相当于不能在同一天买入股票又卖出股票。

如果先更新最小前缀和，再计算前缀和-最小前缀和，就会把空数组的元素和 $0$ 算入答案。

示例 1 $[-2,1,-3,4,-1,2,1,-5,4]$ 的计算流程如下，可以对照代码理解。注意计算顺序。

元素值	前缀和	最小前缀和	前缀和-最小前缀和
$-2$	$-2$	$0$	$-2$
$1$	$-1$	$-2$	$1$
$-3$	$-4$	$-2$	$-2$
$4$	$0$	$-4$	$4$
$-1$	$-1$	$-4$	$3$
$2$	$1$	$-4$	$5$
$1$	$2$	$-4$	$6$
$-5$	$-3$	$-4$	$1$
$4$	$1$	$-4$	$5$

前缀和-最小前缀和的最大值等于 $6$，即为答案。

答疑

问：为什么不能直接计算出最大前缀和与最小前缀和，二者相减不就是答案吗？

答：这是错的。子数组的和必须是右边的前缀和减去左边的前缀和。如果最大前缀和在左边，最小前缀和在右边，就不符合要求。例如 $\mathit{\text{nums}}=[1,-2]$，最大子数组和是 $1$，如果用最大前缀和 $1$ 减去最小前缀和 $-1$，结果是错误的 $2$。

Python 解法1

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = -inf
        min_pre_sum = pre_sum = 0
        for x in nums:
            pre_sum += x  # 当前的前缀和
            ans = max(ans, pre_sum - min_pre_sum)  # 减去前缀和的最小值
            min_pre_sum = min(min_pre_sum, pre_sum)  # 维护前缀和的最小值
        return ans

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN;
        int min_pre_sum = 0;
        int pre_sum = 0;
        for (int x : nums) {
            pre_sum += x; // 当前的前缀和
            ans = max(ans, pre_sum - min_pre_sum); // 减去前缀和的最小值
            min_pre_sum = min(min_pre_sum, pre_sum); // 维护前缀和的最小值
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。仅用到若干额外变量。

方法二：动态规划

定义 $f[i]$ 表示以 $\mathit{\text{nums}}[i]$ 结尾的最大子数组和。

分类讨论：

• $\mathit{\text{nums}}[i]$ 单独组成一个子数组，那么 $f[i]=\mathit{\text{nums}}[i]$。
• $\mathit{\text{nums}}[i]$ 和前面的子数组拼起来，也就是在以 $\mathit{\text{nums}}[i-1]$ 结尾的最大子数组和之后添加 $\mathit{\text{nums}}[i]$，那么 $f[i]=f[i-1]+\mathit{\text{nums}}[i]$。

两种情况取最大值，得

$$f[i]=\{\begin{array}{ll}\mathit{\text{nums}}[i],& i=0\\ max(f[i-1],0)+\mathit{\text{nums}}[i],& i\ge 1\end{array}$$

简单地说，如果 $\mathit{\text{nums}}[i]$ 左边的子数组元素和是负的，就不用和左边的子数组拼在一起了。

答案为 $max(f)$。

⚠注意：答案不是 $f[n-1]$，这仅仅表示以 $\mathit{\text{nums}}[n-1]$ 结尾的最大子数组和。或者说 $f[n-1]$ 意味着 $\mathit{\text{nums}}[n-1]$ 一定要选，但这不一定正确。

答疑

问：为什么不能用「选或不选 $\mathit{\text{nums}}[i]$」的思路做？

答：选或不选无法保证子数组是连续的。选或不选适用于子序列问题（例如 0-1 背包问题），对于子数组问题，更适合用「拼接」的思路，即如果 $\mathit{\text{nums}}[i]$ 左边的子数组元素和是负的，就不用和左边的子数组拼在一起了。

优化前

Python 解法3

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        f = [0] * len(nums)
        f[0] = nums[0]
        for i in range(1, len(nums)):
            f[i] = max(f[i - 1], 0) + nums[i]
        return max(f)

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> f(nums.size());
        f[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            f[i] = max(f[i - 1], 0) + nums[i];
        }
        return ranges::max(f);
    }
};

空间优化

由于计算 $f[i]$ 只会用到 $f[i-1]$，不会用到更早的状态，所以可以用一个变量滚动计算。具体请看视频讲解 动态规划入门：从记忆化搜索到递推。

状态转移方程简化为：

$$f=max(f,0)+\mathit{\text{nums}}[i]$$

$f$ 可以初始化成 $0$ 或者任意负数。

Python 解法5

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = -inf  # 注意答案可以是负数，不能初始化成 0
        f = 0
        for x in nums:
            f = max(f, 0) + x
            ans = max(ans, f)
        return ans

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN; // 注意答案可以是负数，不能初始化成 0
        int f = 0;
        for (int x : nums) {
            f = max(f, 0) + x;
            ans = max(ans, f);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。仅用到若干额外变量。

思考题

1. 改成求最小子数组和，应当如何修改代码？
2. 改成返回和最大的子数组，要怎么做？注意返回的是子数组，不是元素和。
3. 如果子数组的长度有下界，要怎么做？
4. 如果子数组的长度有上界，要怎么做？
5. 如果要求子数组的长度必须是奇数，要怎么做？

欢迎在评论区发表你的思路/代码。

变形题

1. 子数组的元素和有上界。见 363. 矩形区域不超过 K 的最大数值和。提示：枚举上下边界，转成一维数组。
2. 拼接 $k$ 个相同的 $\mathit{\text{nums}}$，得到一个长为 $nk$ 的大数组，求这个大数组的最大子数组和。见 1191. K 次串联后最大子数组之和。
3. $\mathit{\text{nums}}$ 是个环形数组。见 918. 环形子数组的最大和。
4. 删除 $\mathit{\text{nums}}$ 中的至多一个数，再求最大子数组和。见 1186. 删除一次得到子数组最大和。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府