Find Largest sum contiguous Subarray.

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

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

 Constraints:

1 ≤ N ≤ 106
-107 ≤ A[i] <= 107

//Here we are giving the function only

//Kadane's Algorithm

1:  int maxSubarraySum(int arr[], int n)  
2:  {  
3:    int csum = 0 , osum = 0 ;  
4:    for(int i = 0 ; i < n ; i++)  
5:    {  
6:      if(csum >= 0)  
7:      {  
8:       csum += arr[i];    
9:      }  
10:      else  
11:      {  
12:        csum = arr[i];  
13:      }  
14:      if(csum >osum )  
15:      osum = csum;  
16:    }  
17:    return osum;  
18:  }