跳到主要内容

LeetCode-53 最大子数组和

题目描述

来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/maximum-subarray

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

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

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6

题解

暴力法

  • 第一层遍历更新起始位置
  • 第二层求和寻找最大值
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_sub = INT32_MIN;
for(int i = 0; i < nums.size(); ++i) {
int sub = 0;
for(int j = i; j < nums.size(); ++j) {
sub += nums[j];
max_sub = sub > max_sub ? sub : max_sub;
}
}

return max_sub;
}
};
NameValue
时间复杂度O(n2)O(n^2)
空间复杂度O(1)O(1)
  • 存在超时问题

贪心

当遍历到元素为负数时,连续和肯定在变小,贪心的局部最优则是当当前连续和为负数的时候,则放弃当前元素,从下一个元素继续计算连续和,因为当前元素为负数时,下一次相加的连续和只会变小

class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_sub = INT32_MIN;
int sub = 0;
for(int i = 0; i < nums.size(); ++i) {
sub += nums[i];
if(sub > max_sub) {
max_sub = sub;
}
if(sub <= 0) {
sub = 0;
}
}

return max_sub;
}
};
NameValue
时间复杂度O(n)O(n)
空间复杂度O(1)O(1)

动态规划

dp[i]dp[i] 表示以 nums[i]nums[i] 结尾的最大子数组和,那么 dp[i]dp[i] 的状态转移有两种情况

  1. 加入 nums[i]nums[i] 后子数组和变大 dp[i]=dp[i1]+nums[i]dp[i] = dp[i-1] + nums[i]
  2. 从头计算子数组和 dp[i]=nums[i]dp[i] = nums[i]

那么状态转移方程为

dp[i]=max{dp[i1]+nums[i],nums[i]}dp[i] = max\{dp[i-1] + nums[i],nums[i] \}
  • dp[0]=nums[0]dp[0] = nums[0]
  • dp[i]dp[i] 的状态至只与 dp[i1]dp[i-1] 相关,所以还需要创建一个 max_submax\_sub 来维护最大值
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
int max_sub = dp[0];

for(int i = 1; i < n; ++i) {
dp[i] = max(dp[i-1] + nums[i], nums[i]);
if(dp[i] > max_sub) {
max_sub = dp[i];
}
}

return max_sub;
}
};
NameValue
时间复杂度O(n)O(n)
空间复杂度O(n)O(n)

用一个表格方便理解

input: nums = [-2,1,-3,4,-1,2,1,-5,4]

output: 6

连续子数组 [4,-1,2,1] 的和最大,为 6

i012345678
nums[i]-21-34-121-54
dp[i]-21
(-2, 1)
-2
(-2, -3)
4
(-2, 4)
3
(3, -1)
5
(5, 2)
6
(6, 1)
1
(1, -5)
5
(5, 4)
result-21
(-2, 1)
1
(1, -2)
4
(4, 1)
4
(4, 3)
4
(5, 4)
6
(6, 5)
6
(6, 1)
6
(6, 5)
  • 最终返回的 max_submax\_sub 即为最大子数组和

优化动态规划

由于 dp[i]dp[i] 只与 dp[i1]dp[i-1] 相关,并且创建了 max_submax\_sub 来维护最大的和,所以可以优化 dp[n]dp[n] 为一个变量 dpdp 即可

class Solution {
public:
int maxSubArray(vector<int>& nums) {
int dp = 0;
int max_sub = nums[0];

for(const auto i : nums) {
dp = max(dp + i, i);
if(dp > max_sub) {
max_sub = dp;
}
}

return max_sub;
}
};
NameValue
时间复杂度O(n)O(n)
空间复杂度O(1)O(1)

用一个表格方便理解

input: nums = [-2,1,-3,4,-1,2,1,-5,4]

output: 6

连续子数组 [4,-1,2,1] 的和最大,为 6

i012345678
nums[i]-21-34-121-54
dp01
(1, 0)
-2
(-2, -3)
4
(-2, 4)
3
(3, -1)
5
(5, 2)
6
(6, 1)
1
(1, -5)
5
(5, 4)
result-21
(-2, 1)
1
(1, -2)
4
(4, 1)
4
(4, 3)
4
(5, 4)
6
(6, 5)
6
(6, 1)
6
(6, 5)