53. 最大子数组和
一句话套路Kadane:cur 变负就从下一位重启
题目描述
给你一个整数数组 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
提示:
1 <= nums.length <= 105-104 <= nums[i] <= 104
进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。
思路
时间
O(n)空间
O(1)思路
Kadane。定义 f = 「以当前元素结尾」的最大子数组和,f = max(f + x, x):要么接在前面的段后面,要么另起炉灶。
答案是所有 f 的最大值,不是最后的 f —— 这是最常见的错法。
延伸
分治写法 O(n log n),顺便能构造出「跨中点」的信息,面试常追问。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0053 {
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.empty()) return 0; // 力扣保证 n ≥ 1,这里只是不让本地调用碰到 nums[0] 越界
int f = nums[0], ans = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
f = max(f + nums[i], nums[i]);
ans = max(ans, f);
}
return ans;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0053::Solution s;
vector<int> a{-2, 1, -3, 4, -1, 2, 1, -5, 4};
CHECK_EQ(s.maxSubArray(a), 6); // [4,-1,2,1]
vector<int> b{1};
CHECK_EQ(s.maxSubArray(b), 1);
vector<int> c{-1}; // 全负数:答案必须是最大的那个负数,不能是 0
CHECK_EQ(s.maxSubArray(c), -1);
vector<int> d{5, 4, -1, 7, 8};
CHECK_EQ(s.maxSubArray(d), 23);
vector<int> e{};
CHECK_EQ(s.maxSubArray(e), 0); // 空输入不越界(行为不在题面里,仅保证健壮)