HHot 100C++ 图解

53. 最大子数组和

中等 普通数组 4 帧动画 在力扣上做

一句话套路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),顺便能构造出「跨中点」的信息,面试常追问。

图解

-2 0 1 1 -3 2 4 3 -1 4 2 5 1 6 -5 7 4 8
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/05_array.cpp14 行
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;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q53_maximum_subarray11 行
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);  // 空输入不越界(行为不在题面里,仅保证健壮)

↑↓ 选择↵ 打开/ 随时唤起