Kadane's Algorithm

Given an array arr of N integers. Find the contiguous sub-array with maximum sum.

Example 1:

Input:
N = 5
arr[] = {1,2,3,-2,5}
Output:
9
Explanation:
Max subarray sum is 9
of elements (1, 2, 3, -2, 5) which 
is a contiguous subarray.

Example 2:

Input:
N = 4
arr[] = {-1,-2,-3,-4}
Output:
-1
Explanation:
Max subarray sum is -1 
of element (-1)

method 1 :

use sorting:

sort both the string now check if the sorted strings are equal if they are equal return 1, else return 0.

c++ implementation:

 int maxSubarraySum(int a[], int n){
        int max=INT_MIN;int sum=0;
        for(int i=0;i<n;i++)
        {
            sum=sum+a[i];
            if(sum<a[i])
            sum=a[i];
            if(max<sum)
            max=sum;
            
        }
        return max;
        
    }

Time Complexity: O(n) 

space Complexity: O(1)