## Adobe Interview Question Applications Developers

• 0

Given set of N integers (both +ve and -ve), find the continuous subset where the sum is maximum. Return the start and end indices.

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````int maxsum(int arr[], int arraylength, int & startIndex, int & endIndex )
{
int maxsum = arr[0], sum = arr[0];
startIndex = 0,endIndex = 0;
int tempstIndex = 0, tempendIndex = 0;

for(int index =1 ;index < arraylength;index++)
{
if(sum < 0)
{
sum = arr[index];
tempstIndex = tempendIndex = index;
}else{
sum = sum + arr[index];
tempendIndex = index;
}

if(maxsum < sum)
{
maxsum = sum;
startIndex = tempstIndex;
endIndex = tempendIndex;
}
}
return maxsum;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

int maxSum = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < inputList.Length - 1; i++)
{
int tempSum = inputList[i] ;
for (int j = i + 1; j < inputList.Length; j++)
{
tempSum += inputList[j];
if (tempSum > maxSum)
{
maxSum = tempSum;
startIndex = i;
endIndex = j;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Maximum Sum Subarray Problem

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.

Comment hidden because of low score. Click to expand.
0

Incase the maxsum is negative, find the greatest number in the array which is nothing but the maximum sum.

Comment hidden because of low score. Click to expand.
0
of 0 vote

incase of all negative numbers, the maxsum will be negative. At that time, find the greatest number in the array which indicates the maximum sum.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

double maxSubarray(double a[], int numElements)
{
double max=0;
double here=0;
int i;

for(i = 0; i < numElements; i++)
{
here = (here + a[i] > 0) ? here + a[i] : 0;
max = (here > max) ? here : max;
}
return max;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.