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.
We need to use Kadane's Algorithm here
//Kadane's Algorithm
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans =INT_MIN,sum =0;
int n=nums.size();
for(int i=0;i<n;++i){
sum+=nums[i];
ans = max(ans,sum);
if(sum<0)
sum=0;
}
return ans;
}
};
Top comments (0)