Maximum Subarray Sum Kadane Algorithm

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