Given an integer array nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Solution
我们直接用 \(cur\) 来存储当前的总和,当遇到 \(<0\) 的情况直接重新赋值为 \(0\) 即可。
点击查看代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int ans=INT_MIN;
int cur = 0;
for(int i=0;i<n;i++){
cur+=nums[i];
if(cur>ans)ans=cur;
if(cur<0)cur=0;
}
return ans;
}
};