CareerCup

Assumption here is that if all numbers are negative I return 0 . If all the numbers are negative then the solution is -maximum number , which is not difficult to find

This solution will work even if array has all negative numbers.

int maxSubArraySum(int a[], int size)
{
int max_so_far = a[0];
int max_ending_here = 0;
int i;
for(i = 1; i < size; i++) /* start from 2nd element onwards */
{
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;
}

The previous one won't work for all -ve number aray, but i guess the following code would do it.

int maxSubArraySum(int a[], int size)
{
int max_so_far = a[0];
int max_ending_here = 0;
int i;
for(i = 1; i < size; i++) /* start from 2nd element onwards */
{
max_ending_here = max_ending_here + a[i];


if(max_so_far < max_ending_here)
max_so_far = max_ending_here;
}

if(max_ending_here < 0)
max_ending_here = 0;

return max_so_far;
}