Amazon Interview Question
Software Engineer / DevelopersTeam: 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;
}