连续子数组的最大和
输入一个 非空 整型数组，数组里的数可能为正，也可能为负。
数组中一个或连续的多个整数组成一个子数组。
求所有子数组的和的最大值。
要求时间复杂度为 O(n)。
数据范围
数组长度 [1,1000]。
数组内元素取值范围 [−200,200]。
样例
输入：[1, -2, 3, 10, -4, 7, 2, -5]
输出：18
思路1贪心
贪心策略：
- 如果和要变小，那么先取一遍max
- 如果临时和t小于0（此时前面的方案已经不可取，对最大和的贡献是负的）那么将t清0
代码1
点击查看代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
bool f = 0;
int maxn = -300;
for(int i = 0; i < nums.size(); i ++ ){
if(nums[i] >= 0)f = 1;
maxn = max(maxn,nums[i]);
}
int t = 0;
int ans = 0;
if(f){
for(int i = 0; i < nums.size(); i ++ ){
if(nums[i] < 0)ans = max(ans,t);
t += nums[i];
if(t < 0)t = 0;
}
ans = max(ans,t);
return ans;
}
else{
return maxn;
.//如果全部都是负数，那么最大得到数即为最大和
}
}
};
思路2dp
定义\(dp[i]\)为前\(i\)项的最大和.\(dp[1]=nums[1]\)
状态转移方程为\(dp[i] = max(dp[i-1]+nums[i],nums[i])\)
代码2
点击查看代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int dp[nums.size()];
dp[0] = nums[0];
int ans = nums[0];
for(int i = 1; i < nums.size(); i ++ ){
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
ans = max(dp[i],ans);
}
return ans;
}
};
代码3滚动数组优化
由于dp数组只用到了i-1，因此可以考虑用滚动数组进行优化
点击查看代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int a = nums[0],ans = nums[0];
for(auto x:nums){
a = max(a + x, x);
ans = max(a,ans);
}
return ans;
}
};