AcWing55. 连续子数组的最大和
输入一个 非空 整型数组，数组里的数可能为正，也可能为负。
数组中一个或连续的多个整数组成一个子数组。
求所有子数组的和的最大值。
要求时间复杂度为 O(n)。
数据范围
数组长度 [1,1000]。
数组内元素取值范围 [−200,200]
样例
输入：[1, -2, 3, 10, -4, 7, 2, -5]
输出：18解析：
思路一：s变量记录当遍历到第 i 个数时，前 i - 1 个数组成的连续子数组的最大和。
所以s有正、非正两种情况。
1. s为正，加上 s[i] 并且更新res。
2. s非正，如果继续加则没有意义，先令 s 为0，加上 s[i] 并且更新res。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res=-0x3f3f3f3f,s;
for(auto it:nums){
if(s<0) s=0;
s+=nums[i];
res=max(res,s);
}
return res;
}
};思路二：当遍历到第 i 个数时，只有加或者不加两种情况，判断谁更大即可，然后更新res
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res=-0x3f3f3f3f,dp[1010];
nums.insert(nums.begin(),0);
for(int i=1;i<nums.size();i++){
dp[i]=max(dp[i-1]+nums[i],nums[i]);
res=max(res,dp[i]);
}
return res;
}
};