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;
}
};
Name | Value |
---|---|
时间复杂度 | |
空间复杂度 |
- 存在超时问题
贪心
当遍历到元素为负数时,连续和肯定在变小,贪心的局部最优则是当当前连续和为负数的时候,则放弃当前元素,从下一个元素继续计算连续和,因为当前元素为负数时,下一次相加的连续和只会变小
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;
}
};
Name | Value |
---|---|
时间复杂度 | |
空间复杂度 |
动态规划
用 表示以 结尾的最大子数组和,那么 的状态转移有两种情况
- 加入 后子数组和变大
- 从头计算子数组和
那么状态转移方程为
- 的状态至只与 相关,所以还需要创建一个 来维护最大值
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;
}
};
Name | Value |
---|---|
时间复杂度 | |
空间复杂度 |
用一个表格方便理解
input: nums = [-2,1,-3,4,-1,2,1,-5,4]
output: 6
连续子数组 [4,-1,2,1] 的和最大,为 6
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
nums[i] | -2 | 1 | -3 | 4 | -1 | 2 | 1 | -5 | 4 |
dp[i] | -2 | 1 (-2, 1) | -2 (-2, -3) | 4 (-2, 4) | 3 (3, -1) | 5 (5, 2) | 6 (6, 1) | 1 (1, -5) | 5 (5, 4) |
result | -2 | 1 (-2, 1) | 1 (1, -2) | 4 (4, 1) | 4 (4, 3) | 4 (5, 4) | 6 (6, 5) | 6 (6, 1) | 6 (6, 5) |
- 最终返回的 即为最大子数组和
优化动态规划
由于 只与 相关,并且创建了 来维护最大的和,所以可以优化 为一个变量 即可
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;
}
};
Name | Value |
---|---|
时间复杂度 | |
空间复杂度 |
用一个表格方便理解
input: nums = [-2,1,-3,4,-1,2,1,-5,4]
output: 6
连续子数组 [4,-1,2,1] 的和最大,为 6
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
nums[i] | -2 | 1 | -3 | 4 | -1 | 2 | 1 | -5 | 4 |
dp | 0 | 1 (1, 0) | -2 (-2, -3) | 4 (-2, 4) | 3 (3, -1) | 5 (5, 2) | 6 (6, 1) | 1 (1, -5) | 5 (5, 4) |
result | -2 | 1 (-2, 1) | 1 (1, -2) | 4 (4, 1) | 4 (4, 3) | 4 (5, 4) | 6 (6, 5) | 6 (6, 1) | 6 (6, 5) |