53. 最大子数组和
题目描述
输入整数数组 nums。子数组指数组中连续的一段，且至少含一个元素。
在所有子数组中找出元素和最大的那个，返回这个最大和。
示例 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
解释：取整个数组，和为 5+4-1+7+8 = 23。
数据范围
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
进阶：写出 O(n) 解法之后，试着再用分治的思路解一遍。
解题思路：动态规划（Kadane）
以 current 表示必须以当前位置结尾的最大和：若此前和为负就从当前数重新开始，否则接上；同步更新全局 best。
为什么正确
current 是所有以当前下标结尾的非空子数组中的最大和。
复杂度分析
时间 O(n)，额外空间 O(n)：Python 的 nums[1:] 会创建长度 n-1 的列表切片。
易错点
初始化为 0 会在全负数组时错误返回 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxSubArray(self, nums):
current=best=nums[0]
for x in nums[1:]:
current=max(x,current+x)
best=max(best,current)
return bestclass Solution {
public int maxSubArray(int[] nums) {
int current = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
current = Math.max(x, current + x);
best = Math.max(best, current);
}
return best;
}
}class Solution {
public:
int maxSubArray(vector<int>& nums) {
int current = nums[0], best = nums[0];
for (int i = 1; i < (int)nums.size(); i++) {
int x = nums[i];
current = max(x, current + x);
best = max(best, current);
}
return best;
}
};func maxSubArray(nums []int) int {
current, best := nums[0], nums[0]
for _, x := range nums[1:] {
current = max(x, current+x)
best = max(best, current)
}
return best
}var maxSubArray = function(nums) {
let current = nums[0], best = nums[0];
for (const x of nums.slice(1)) {
current = Math.max(x, current + x);
best = Math.max(best, current);
}
return best;
};function maxSubArray(nums: number[]): number {
let current = nums[0], best = nums[0];
for (const x of nums.slice(1)) {
current = Math.max(x, current + x);
best = Math.max(best, current);
}
return best;
}其他解法
Kadane 与前缀和都是一次遍历、最简洁；分治同样线性，但能扩展成线段树处理区间查询和单点修改。
解法 2：前缀和 + 最小前缀 时间 O(n)，空间 O(1)
子数组和等于两个前缀和之差。从左到右累加前缀和 pre，同时记录此前出现过的最小前缀和 min_pre（初始为 0，对应空前缀）。每一步用 pre - min_pre 更新答案，再用 pre 更新 min_pre。
和 Kadane 一样是一次遍历。它把问题转成“买卖股票”式的差值最大化，便于推广到带长度限制等前缀和类问题。
class Solution:
def maxSubArray(self, nums):
best = nums[0]
pre = 0
min_pre = 0
for x in nums:
pre += x
best = max(best, pre - min_pre)
min_pre = min(min_pre, pre)
return bestclass Solution {
public int maxSubArray(int[] nums) {
int best = nums[0], pre = 0, minPre = 0;
for (int x : nums) {
pre += x;
best = Math.max(best, pre - minPre);
minPre = Math.min(minPre, pre);
}
return best;
}
}class Solution {
public:
int maxSubArray(vector<int>& nums) {
int best = nums[0], pre = 0, minPre = 0;
for (int x : nums) {
pre += x;
best = max(best, pre - minPre);
minPre = min(minPre, pre);
}
return best;
}
};func maxSubArray(nums []int) int {
best, pre, minPre := nums[0], 0, 0
for _, x := range nums {
pre += x
if pre-minPre > best {
best = pre - minPre
}
if pre < minPre {
minPre = pre
}
}
return best
}var maxSubArray = function(nums) {
let best = nums[0], pre = 0, minPre = 0;
for (const x of nums) {
pre += x;
best = Math.max(best, pre - minPre);
minPre = Math.min(minPre, pre);
}
return best;
};function maxSubArray(nums: number[]): number {
let best = nums[0], pre = 0, minPre = 0;
for (const x of nums) {
pre += x;
best = Math.max(best, pre - minPre);
minPre = Math.min(minPre, pre);
}
return best;
}解法 3：分治 时间 O(n)，空间 O(log n)
把区间从中点分成左右两半，分别求出四个量：区间和、最大前缀和、最大后缀和、最大子数组和。合并时，最大前缀和取左前缀与“左区间和 + 右前缀”的较大者，后缀同理。最大子数组和取左答案、右答案、“左后缀 + 右前缀”三者的最大值。
代码更长，递归栈占 O(log n)。它的价值在于合并规则可以直接放进线段树，支持多次查询任意区间的最大子数组和。
class Solution:
def maxSubArray(self, nums):
# 返回 (区间和, 最大前缀和, 最大后缀和, 最大子数组和)
def solve(lo, hi):
if lo == hi:
x = nums[lo]
return x, x, x, x
mid = (lo + hi) // 2
ls, lp, lsuf, lbest = solve(lo, mid)
rs, rp, rsuf, rbest = solve(mid + 1, hi)
total = ls + rs
pre = max(lp, ls + rp)
suf = max(rsuf, rs + lsuf)
best = max(lbest, rbest, lsuf + rp)
return total, pre, suf, best
return solve(0, len(nums) - 1)[3]class Solution {
// 返回 {区间和, 最大前缀和, 最大后缀和, 最大子数组和}
int[] solve(int[] nums, int lo, int hi) {
if (lo == hi) {
int x = nums[lo];
return new int[]{x, x, x, x};
}
int mid = (lo + hi) / 2;
int[] l = solve(nums, lo, mid), r = solve(nums, mid + 1, hi);
int total = l[0] + r[0];
int pre = Math.max(l[1], l[0] + r[1]);
int suf = Math.max(r[2], r[0] + l[2]);
int best = Math.max(Math.max(l[3], r[3]), l[2] + r[1]);
return new int[]{total, pre, suf, best};
}
public int maxSubArray(int[] nums) {
return solve(nums, 0, nums.length - 1)[3];
}
}class Solution {
public:
struct Info {
int total, pre, suf, best;
};
Info solve(vector<int>& nums, int lo, int hi) {
if (lo == hi) {
int x = nums[lo];
return {x, x, x, x};
}
int mid = (lo + hi) / 2;
Info l = solve(nums, lo, mid), r = solve(nums, mid + 1, hi);
Info res;
res.total = l.total + r.total;
res.pre = max(l.pre, l.total + r.pre);
res.suf = max(r.suf, r.total + l.suf);
res.best = max(max(l.best, r.best), l.suf + r.pre);
return res;
}
int maxSubArray(vector<int>& nums) {
return solve(nums, 0, nums.size() - 1).best;
}
};type info struct {
total, pre, suf, best int
}
func maxSubArray(nums []int) int {
var solve func(lo, hi int) info
solve = func(lo, hi int) info {
if lo == hi {
x := nums[lo]
return info{x, x, x, x}
}
mid := (lo + hi) / 2
l, r := solve(lo, mid), solve(mid+1, hi)
return info{
total: l.total + r.total,
pre: max(l.pre, l.total+r.pre),
suf: max(r.suf, r.total+l.suf),
best: max(l.best, r.best, l.suf+r.pre),
}
}
return solve(0, len(nums)-1).best
}var maxSubArray = function(nums) {
// 返回 [区间和, 最大前缀和, 最大后缀和, 最大子数组和]
const solve = (lo, hi) => {
if (lo === hi) {
const x = nums[lo];
return [x, x, x, x];
}
const mid = (lo + hi) >> 1;
const l = solve(lo, mid), r = solve(mid + 1, hi);
return [
l[0] + r[0],
Math.max(l[1], l[0] + r[1]),
Math.max(r[2], r[0] + l[2]),
Math.max(l[3], r[3], l[2] + r[1]),
];
};
return solve(0, nums.length - 1)[3];
};function maxSubArray(nums: number[]): number {
// 返回 [区间和, 最大前缀和, 最大后缀和, 最大子数组和]
const solve = (lo: number, hi: number): number[] => {
if (lo === hi) {
const x = nums[lo];
return [x, x, x, x];
}
const mid = (lo + hi) >> 1;
const l = solve(lo, mid), r = solve(mid + 1, hi);
return [
l[0] + r[0],
Math.max(l[1], l[0] + r[1]),
Math.max(r[2], r[0] + l[2]),
Math.max(l[3], r[3], l[2] + r[1]),
];
};
return solve(0, nums.length - 1)[3];
}