# 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)