This content originally appeared on DEV Community and was authored by DEV Community
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;
}
};
This content originally appeared on DEV Community and was authored by DEV Community
Print
Share
Comment
Cite
Upload
Translate
Updates
There are no updates yet.
Click the Upload button above to add an update.
APA
MLA
DEV Community | Sciencx (2022-02-22T16:43:11+00:00) Maximum Subarray – Leetcode Solution. Retrieved from https://www.scien.cx/2022/02/22/maximum-subarray-leetcode-solution/
" » Maximum Subarray – Leetcode Solution." DEV Community | Sciencx - Tuesday February 22, 2022, https://www.scien.cx/2022/02/22/maximum-subarray-leetcode-solution/
HARVARDDEV Community | Sciencx Tuesday February 22, 2022 » Maximum Subarray – Leetcode Solution., viewed ,<https://www.scien.cx/2022/02/22/maximum-subarray-leetcode-solution/>
VANCOUVERDEV Community | Sciencx - » Maximum Subarray – Leetcode Solution. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2022/02/22/maximum-subarray-leetcode-solution/
CHICAGO" » Maximum Subarray – Leetcode Solution." DEV Community | Sciencx - Accessed . https://www.scien.cx/2022/02/22/maximum-subarray-leetcode-solution/
IEEE" » Maximum Subarray – Leetcode Solution." DEV Community | Sciencx [Online]. Available: https://www.scien.cx/2022/02/22/maximum-subarray-leetcode-solution/. [Accessed: ]
rf:citation » Maximum Subarray – Leetcode Solution | DEV Community | Sciencx | https://www.scien.cx/2022/02/22/maximum-subarray-leetcode-solution/ |
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.