Kadane Algorithm Geeks For Geeks
class Solution{
// arr: input array
// n: size of array
//Function to find the sum of contiguous subarray with maximum sum.
int maxSubarraySum(int arr[], int n){
int count=0;
int max1=arr[0];
int max=0;
for(int i=0;i<n;i++){
if(arr[i]<0){
count++;
}
}
if(count==n){
for(int i=1;i<n;i++){
if(arr[i]>max1){
max1=arr[i];
}
}
return max1;
}
else{
int sum=0;
max=arr[0];
for(int i=0;i<n;i++){
sum=sum+arr[i];
if(sum<0){
sum=0;
}
if(sum>max){
max=sum;
}
}
}
return max;
}
}
Approach: Here we will traverse the array and we will see whether all elements in the array are negative or not.
If all the elements are negative then we will simply take one element max1 and after iterating the array we will see if any other element has a value less than that (in a negative sense ) then we modify the value of max1.
Else there will mix of positive and negative elements. In that case, we will have one element max which will point to arr[0]. Then while traversing we will see if the sum of an incoming element with the existing sum variable is negative we will modify the value of the sum variable to 0 else we will traverse further. While traversing we will also keep the look at the value of max if anytime it is more than the sum we will modify it.
Time:O(N) Iterating loop.
Space:O(1) Not using any additional data structure.
Thanks for Reading.😇
Comments
Post a Comment