题目描述
给你一个数列nums,让你求出其中的最大子段和。
样例
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
我太蒟了,只会O(n)级别的!!!
(dp) $O(n)$
从1到n进行遍历,并用变量sum累计,将只选择当前数字与当前数字+sum比较,取较大值赋给sum
注意:ans是在循环中求最大值,因为我们并不保证最大子段和中包含最后一个数
C++ 代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum=nums[0],ans=nums[0];
for(int i=1;i<nums.size();i++)
{
sum=max(sum+nums[i],nums[i]);
ans=max(ans,sum);
}
return ans;
}
};