Adobe Interview Question
Applications DevelopersCountry: India
Interview Type: In-Person
public static int getMax(int[] arr){
int maxsum=0;
int sum=0;
for(int i=0;i<arr.length;i++){
sum+=arr[i];
if(maxsum < sum)
maxsum=sum;
else if(sum<0)
sum=0;
}
return maxsum;
}
Note:It will not work if array has all negative values.
Source code : Time complexity = O(n), Space complexity = O(1)
void find_max_sum(int *arr, int n, int *start, int *end, int *sum)
{
int i, temp_sum, temp_start, temp_end;
*end = *start = temp_start = temp_end = -1;
*sum = temp_sum = 0;
for(i = 0; i < n; i++)
{
temp_sum += arr[i];
if(temp_sum < 0)
{
temp_sum = 0;
temp_start = temp_end = -1;
}
else if(temp_sum > 0)
{
if(temp_start == -1)
temp_start = i;
temp_end = i;
}
if(temp_sum > *sum)
{
*start = temp_start;
*end = temp_end;
*sum = temp_sum;
}
}
}
Its just Kadane's algo...Java implementation would go like this
public static void implementAlgo(int[] pArray) {
int max_so_far = 0;
int max_ending_here = 0;
int maxStart=0;
int maxEnd=0;
int currentStart=0;
for(int i=0;i<pArray.length;i++){
max_ending_here=max_ending_here+pArray[i];
if(max_ending_here<0){
max_ending_here=0;
currentStart=i+1;
}
if(max_so_far<max_ending_here){
max_so_far=max_ending_here;
maxStart=currentStart;
maxEnd=i;
}
}
System.out.println("Max="+max_so_far);
System.out.println("Started from:"+maxStart);
System.out.println("Ended at :"+maxEnd);
}
- naveentiptur May 29, 2012