kadanes algorithm.

 Question is:

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)

THE CODE TO SOLVE THIS QUESTION IS:

 int maxSubarraySum(int arr[], int n){
    
  int max_so_far=INT_MIN;
  int max_uptohere=0;
  for(int i=0;i<n;i++)
  {
      max_uptohere=max_uptohere+arr[i];
      if(max_uptohere<0)
      {
          max_uptohere=0;
      }
      if(max_so_far<max_uptohere)
      {
          max_so_far=max_uptohere;
      }
   
  }
   return max_so_far; 
}