Largest Sum Contiguous Subarray

Kadane's algorithm : 
Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this).

 

int maxSubArraySum(int a[], int size)

{

   int max_so_far = 0, max_ending_here = 0;

   int i;

   for(i = 0; i < size; i++)

   {

     max_ending_here = max_ending_here + a[i];

     if(max_ending_here < 0)

        max_ending_here = 0;

     if(max_so_far < max_ending_here)

        max_so_far = max_ending_here;

    }

    return max_so_far;

}