题目

53. 最大子数组和

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

1
2
3
4
5
6
7
8
9
10
11
12
示例 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

思路一:贪心

说明

最简单的方式可以用一个三层的嵌套遍历找到这个最大值,时间复杂度是O(N^3)。但这样写肯定是不好的。

题目要求的是一个连续子数组的和,我们可以认为遍历到某一个数的时候,这个子数组的和就是到前一位的子数组和+当前值,这时候就会出现两种情况

  • 前一位的数组和+当前值 < 当前值,这说明前一位的子数组和是一个负数,那还不如当前值自己大,所以直接选用当前值作为新一轮子数组的开始。
  • 前一位的数组和+当前值 >= 当前值,可以将当前值算到前一位的这个子数组中,继续扩张。

每一次操作之后都需要更新最大和。

我们可以另外开辟一个数组来存放每一位的最大子数组和,再通过下标访问前一位的数组和。但实际上每一次遍历只和前一位的子数组和有关系,所以直接用int来存放前一位的子数组和就够了,不需要额外开辟数组的空间复杂度消耗了。

代码1

代码比较简单,理解了思路就能写出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int prev = 0; // 之前的最大子数组和,初始值0
int maxNum = nums[0]; // 从数组中选一个值
for (auto& i : nums) {
// 如果之前的最大子数组和还没有我自己大,则从我自己开始新列一个子数组
prev = max(prev + i, i);
// 更新最大值
maxNum = max(maxNum, prev);
}
return maxNum;
}
};

image.png

时间复杂度O(N),空间复杂度O(1)

代码2

上面这个代码乍一看可能不好理解,我们可以按下面的方式写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ret = INT32_MIN;
int sum = 0;
for (auto& i : nums) {
sum += i;
// 更新最大值
if (sum > ret) {
ret = sum;
}
// 如果当前sum为负数,那么需要重新开子数组了
// 因为当前的sum加上下一位后,肯定没有下一位本身大!
if (sum <= 0) {
sum = 0; // 重置为0
}
}
return ret;
}
};

这个思路也是一样,只不过将判断换到了当前位之后就处理了

  • 维护一个sum,作为当前子数组的和;
  • 每一次都让sum+=i,并更新最大值;
  • 如果当前sum小于等于0了,当前子数组的和+下一位肯定会小于下一位本身,此时置为0,从下一位开始重新计算一个新的子数组和;
  • 直到遍历完毕返回维护的最大值。

两个写法都能过,重点还是理解思路啦!

image.png

思路二:动态规划

说明

用动态规划的思路来思考这道题目,首先是确定dp数组的含义

  • dp[i]代表以i为结尾(包括i)的最大连续子数组和。

那么状态转移就有两种情况:

  1. 将当前元素计入子数组,即dp[i] = nums[i] + dp[i-1]
  2. 从当前元素开始重新记录一个新的子数组,即只保留nums[i]

我们用max函数选取这两个情况中的最大值就可以了。

从递推公式中可以得知,dp[i]依赖于dp[i-1],所以需要初始化dp[0],显然dp[0] = nums[0],因为第一位元素开始的子数组只有他自己。

初始化完毕后,从下标1开始遍历nums数组就可以了。

代码

从这个代码能看出来,虽然我们是用了dp数组这种比较“标准”的方式来进行解题的,但它本质上和上文中使用的贪心算法没有特别大的区别。根本上的思路完全一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// i下标为结尾的最长连续子数组的最大和
vector<int> dp(nums.size(), 0);
dp[0] = nums[0]; // 初始化
int result = nums[0]; // 最大值
for (int i = 1; i < nums.size(); i++) {
// 判断是沿用当前的子数组,还是从当前位置新开一个子数组
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
if (dp[i] > result) {
result = dp[i];
}
}
return result;
}
};

image.png

The end

这道题还有很多不同的解法,可以参考这个博客:连续子数组的最大和问题(五种解法)