Problem:53. 最大子数组和
题目描述
给你一个整数数组 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 <= 10^5
- -10^4 <= nums[i] <= 10^4
解法一：前缀和暴力解
看到和最大的连续数组，我第一时间就想到的是前缀和，预处理前缀和，两重循环维护一个区间，每次判断是否是最优解即是否最大。代码如下：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> sum(n);
sum[0] = nums[0];
for(int i = 1;i < n;i++) sum[i] = sum[i–1] + nums[i];
int res = sum[0];
for(int i = 0;i < n;i++) {
for(int j = i;j < n;j++) {
if(i == 0) res = max(res,sum[j]);
else res = max(res,sum[j] – sum[i–1]);
}
}
return res;
}
};
⏱️ 时间复杂度：
O
(
N
2
)
O(N^2)
O(N2)
优化一：
假设一个子数组下标 [i,j] ，子数组的和 = sum[j] – sum[i-1]，观察这个式子，要想让子数组的和最大，由于 sum[j] 经过前缀和预处理后是不变的确定的数，因此只需要找到在 j 之前的一个最小的前缀和 sum[i-1] ，此时的 sum[j] – sum[i-1] 最大，遍历每个位置时比较并确定最大值即可。 一句话总结就是当前前缀和减去前面最小的前缀和。
⚠️注意：前面最小的前缀和 > 0 怎么办？ 前面最小的前缀和 > 0 时当前前缀和就是最大的，不需要再减了，因此我们将 min_pre = 0 即初始化为 0 ，min_pre = min(min_pre,sum[i]) 这样只有前缀和 < 0 才会更新 min_pre。
具体代码如下：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> sum(n);
sum[0] = nums[0];
for(int i = 1;i < n;i++) sum[i] = sum[i–1] + nums[i];
int ans = sum[0];
int min_pre = 0;
for(int i = 0;i < n;i++) {
ans = max(ans,sum[i] – min_pre);
min_pre = min(min_pre,sum[i]);
}
return ans;
}
};
⏱️ 时间复杂度：
O
(
N
)
O(N)
O(N)
优化二:
上面的优化思路是当前的前缀和减去前面（< 0 的）最小的前缀和，那么我们可不可以，直接跳过那一段负的，例如我们假设 sum[i-1] < 0 ，那么我们直接从 i 开始叠加，因为前 i-1 个元素的和对最大值是负贡献，直接舍弃这一段即可，这样也就不用预处理前缀和数组了，更加简洁。 具体代码如下：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int ans = nums[0];
int sum = 0;
for(int i = 0;i < n;i++) {
if(sum < 0) sum = nums[i];
else sum += nums[i];
// 或者直接 sum = max(sum,sum + nums[i]);
ans = max(ans,sum);
}
return ans;
}
};
解法二：动态规划
上面前缀和的过程中 ans = max(ans,sum[i] – min_pre) 表示比较上一个位置的最大子数组和当前位置的最大子数组并更新，从这个结构中可以看出该问题具有最优子结构的特性，因此我们定义一个状态数组 dp，其中 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。 对于每一个 dp[i] ：
- dp[i-1] >= 0 时 dp[i] = dp[i-1] + nums[i]；
- dp[i-1] < 0 时 dp[i] = nums[i]。
这个思路和解法一优化的思路一致。 于是我们得到了状态转移方程：
d
p
[
i
]
=
max
(
n
u
m
s
[
i
]
,
d
p
[
i
−
1
]
+
n
u
m
s
[
i
]
)
dp[i] = \\max(nums[i], \\quad dp[i-1] + nums[i])
dp[i]=max(nums[i],dp[i−1]+nums[i]) 代码如下：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
int ans = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = max(nums[i], dp[i–1] + nums[i]);
ans = max(ans, dp[i]);
}
return ans;
}
};
⏱️ 时间复杂度：
O
(
N
)
O(N)
O(N)
💡 深度解析：殊途同归的算法之美
仔细对比可以发现，本解法与 解法一（优化一） 的代码逻辑惊人地相似。
-
若将解法一改为在循环中累加而非预处理前缀和数组，两者的代码将完全重合。
-
若将本解法通过“滚动变量”去掉 dp 数组，也与优化二完全一致。
这两种看似不同的切入点——一个着眼于 “区间差值” (前缀和)，一个着眼于 “状态转移” (DP)，最终在代码实现上却达到了 殊途同归 的效果。这也深刻地说明了：本题中“寻找最小前缀和”的贪心策略，本质上就是动态规划状态转移的另一种表现形式。
❤️ 最后
新人up，如有不足还请多多指正，欢迎交流！ 如果内容对你有帮助的话，还请点赞支持一下喽🙏🙏 你的支持是我前进的最大动力！！ up正在更新力扣hot100的题目，有需要的朋友欢迎点赞、收藏加关注哦！
