# Maximum Subarray Sum Kadane Algorithm

In this program, we are going to find the maximum subarray sum. Maximum sub-array is defined in terms of the sum of the elements in the sub-array.
In this program, we are going to find the maximum subarray sum.
Subarray: Continous part of an array. Maximum sub-array is defined in terms of the sum of the elements in the sub-array

## Maximum Subarray Sum using Kadane Algorithm

```int kadane(int * arr,int n)
{
int curr_sum=0;
int mx=INT_MIN;
for(int i=0;i<n;i++)
{
curr_sum+=arr[i];
mx=max(mx,curr_sum);

if(curr_sum<0)
curr_sum=0;
}
return mx;
}

```

## Maximum Subarray using Recursion

```int maxSubArray(vector<int>  &arr,int & ans,int i=0) {
if(i==arr.size())
return 0;
int temp=maxSubArray(arr,ans,i+1);
int op1=arr[i]+ (temp>0?temp:0);
ans=max(ans,op1);
return op1;
}
int maxSubArray(vector<int>  & arr) {
int ans=INT_MIN;
maxSubArray(arr,ans,0);
return ans;
}
```

## Maximum Subarray Sum Leetcode Solution

```class Solution {
public:
int maxSubArray(vector <int> & arr) {
int n=arr.size();
int curr_sum=0;
int mx=INT_MIN;
for(int i=0;i<n;i++)
{
curr_sum+=arr[i];
mx=max(mx,curr_sum);

if(curr_sum<0)
curr_sum=0;
}
return mx;
}
};
```

## Maximum Sub Array GFG Solution

In this problem, we have to return the subarray having a maximum sum.
1. Find the maximum sum using the kadane algorithm and store it in variable k.
2. Find the longest subarray of sum k
```vector<int> findSubarray(int arr[], int n) {
// code here

long long int curr_sum=0;
long long int mx=INT_MIN;
for(int i=0;i<n;i++)
{
if(arr[i]<0)
{
curr_sum=0;
continue;
}

curr_sum+=arr[i];
mx=max(mx,curr_sum);

}
long long int k=mx;
//cout<<k<<endl;
if(mx<0)
{
return {-1};
}
vector<int> ans;
long long int i=0,j=0;
long long int mx2=0;
long long int sum=0;
int startIndex=-1,endIndex=-1;
while(i<n && j<n)
{
if(arr[j]<0)
{
sum=0;
j++;
i=j;
continue;
}

sum+=arr[j];
if(sum<k)
{
j++;
}
else
if(sum==k)
{
if(mx2<j-i+1)
{
startIndex=i;
endIndex=j;
mx=j-i+1;
}
j++;
}

}
//cout<<startIndex<<" "<<endIndex<<endl;

for(int i=startIndex;i<=endIndex;i++)
{
ans.push_back(arr[i]);
}

return ans;
}

```
This is all about the Maximum Subarray Sum Kadane Algorithm. Thanks for reading this blog post. If you have any doubts regarding this problem, let me know in the comment section

### 1 comment

1. Great post, nice explanation.