## Amazon Interview Question

Software Engineer / Developers**Team:**Data Storage

**Country:**India

**Interview Type:**Phone Interview

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;

}

yo kadanes algorithm will surely work here :)

- geeks September 16, 2011int Maxsubarray(int a[],int n)

{

int sum,maxsum=INT_MIN;

int i,j;

j=0;

start=j;

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

{

sum=sum+a[i];

if(sum>maxsum)

{

maxsum=sum;

end=i;

}

if(sum<0)

{

j=i;

start=j;

sum=0;

}

}

return maxsum;

}