## Sap Labs Interview Question for Developer Program Engineers

Team: Potsdam
Country: Germany
Interview Type: Phone Interview

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

Here is my answer to this question:

basicalgos.blogspot.com/2012/05/52-find-sub-array-of-max-sum.html

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

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

``````public static void printMaxSum(int[] a) {
if (a == null || a.length == 0) return;
int len = a.length;
int max=a[0], maxi=0, maxj=0;
int sum=a[0], i=0;

for (int j=1; j<len; j++) {
if (sum <= 0 || sum + a[j] <= 0) {
sum = a[j];
i = j;
} else {
sum += a[j];
}
if (sum > max) {
max = sum;
maxi = i;
maxj = j;
}
}
System.out.println("\nmaxi, maxj, and max are: " + maxi + "," + maxj + "," + max);
}

O(n)``````

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

For {0,0,-1,-2,-3} input the output should be i=0, j=1. Does the code you have sent return these values?

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

Thats right. A simple way to visualize this is to plot a curve of the recurring sum and take the starting and ending values as range values and the value of the peak as the sum.

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

my solution is using DP by filling the matrix with the sum values. The matrix column is i, the matrix row is j. First fill cells (i,i) with the values from the input array: M[i,i] = input[i]; Then fill the left side of matrix diagonal starting from [n-1, n-2] cell by using previously calculated values, i.e. M[7, 6] = M[7,7] + M[6,6]; M[7,5] = M[7,6] + M [5,5], etc. Finally find the max element in matrix. If no additional data structures are allowed then just go through array and calculate the value for each interval.

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

DP
public static void findStartAndEnd(int [] array){
int [] state=new int [array.length];
state[0]=array[0];
int max=state[0];
int start=0;
int end=0;

for (int i=1;i<array.length;++i){
if (state[i-1]+array[i]<=0){
state[i]=0;
start=i+1;
}else{
state[i]=state[i-1]+array[i];
if (state[i]>max){
max=state[i];
end=i;
}
}
}

System.out.println("SUM: "+max);
System.out.println("START: "+start);
System.out.println("END: "+end);
}

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

dp below is an array of state

``````struct state {
int S, E, maxval;
};``````

This is the routine that will populate the dp array with max-sum starting from i (to j)

``````FOR(i, 1, n) {
if (a[i] > 0) {
RFOR(j, i-1, 0) {
if (dp[j+1].maxval > 0) {
dp[j].maxval = a[j] + dp[j+1].maxval;
dp[j].E = i;
} else {
break;  // do not proceed further
}
}
}
}``````

To get the max-state run over the dp and output the results. O(n^2)

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

Using Kdane's algorithm it can be done in O(n) and O(k) space.

func(int[] a) {
int startIndex=-1,endIndex=-1,maxEndingHere=0,maxSoFar=0;
int tempStartIndex=-1,tempEndIndex=-1;
for (int i=0;i<a.length;i++) {
//finding the maximum sum of all arrays that end at i
if (a[i] >= maxEndingHere+a[i]) {
tempStartIndex=tempEndIndex=i;
maxEndingHere = a[i];
} else {
tempEndIndex=i;
maxEndingHere = maxEndingHere+a[i];
}
//The maximum sum so far will be the sum of all the subarrays considered so far or all the
// sub arrays ending at this position.

if (maxEndingHere >= maxSoFar) {
startIndex = tempStartIndex;
endIndex = tempEndIndex;
maxSoFar = maxEndingHere;
}
}
return startIndex,endIndex;
}

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

``(Y)``

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

``````#include<stdio.h>
int main()
{
int a[10]={3,2,-3,1,-10,-15,12,-3,11,12};
int sum=0,start,end;
int maxsum=0;
int i,j;
for(i=0;i<10;i++)
{
sum=0;
for(j=i;j<10;j++)
{
sum = a[j] + sum;
if(sum>maxsum)
{
maxsum=sum;
start = i;
end = j;
}}
}
printf("%d\n",maxsum);
printf("start = %d , end = %d \n" ,start,end);
return 0;
}``````

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

``````#include<stdio.h>
#include<conio.h>
#define ub 7
int main()
{
int a[]={1,3,8,2,-1,10,-2,1};
int temp=a[1],highestindex,sum,lindex,index,uindex;
for(int i=0;i<=ub;i++)
if(temp<a[i])
highestindex=i;
printf("highest elemnt is %d",a[highestindex]);

temp=0;
sum=0;

index=lindex=highestindex;
while(index>0)
{
index--;
sum=sum+a[index];
if(sum>temp)
{
temp=sum;
lindex=index;
printf("lindex %d\n",lindex);
}

}
printf(" lb is %d  ",a[lindex]);

temp=0;
sum=0;

index=uindex=highestindex;
while(index<ub)
{
index++;
sum=sum+a[index];
if(sum>temp)
{
temp=sum;
uindex=index;
}
}
printf(" ub is %d",a[uindex]);

getch();
}``````

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

``````#include<stdio.h>
#include<conio.h>
struct ret
{
int lindex;
int rindex;
int sum;
};
struct ret find_max_cross_array( int arr[],int low, int mid ,int high);
struct ret find_max_subarray( int arr[],int low,int high);

int main()
{
int arr[10]={20,12,-10,8,-61,-8,-5,4,26,-2};
struct ret h;
h=find_max_subarray(arr,0,9);
printf("%d %d %d ",h. lindex,h.rindex,h.sum);
getch();
}
struct ret find_max_subarray( int arr[],int low,int high)
{
int cross_sum,cross_lindex,cross_rindex,right_sum,left_sum,left_lindex,left_rindex,right_lindex,right_rindex,mid;
if(low==high)
{
struct ret b;
b.lindex=low;
b.rindex=high;
b.sum=arr[low];
return(b);
//return(low,high,arr[low]);
}
else
{
struct ret c;
mid=(low+high)/2;
c=find_max_subarray(arr,low,mid);/////////////////
left_lindex=c.lindex;
left_rindex=c.rindex;
left_sum=c.sum;
c=find_max_subarray(arr,mid+1,high);//////////////
right_lindex=c.lindex;
right_rindex=c.rindex;
right_sum=c.sum;
c=find_max_cross_array(arr,low,mid,high);/////////
cross_lindex=c.lindex;
cross_rindex=c.rindex;
cross_sum=c.sum;
if(left_sum>right_sum)
{
right_sum=left_sum;
right_lindex=left_lindex;
right_rindex=left_rindex;
}
if(cross_sum>right_sum)
{
right_sum=cross_sum;
right_lindex=cross_lindex;
right_rindex=cross_rindex;
}
c.lindex=right_lindex;
c.rindex=right_rindex;
c.sum=right_sum;
return(c);
}

}
struct ret find_max_cross_array( int arr[],int low, int mid ,int high)
{
struct ret a;
int leftsum,j,rightsum,sum,maxleft,maxright;
leftsum=-10000000;
sum=0;
for(j=mid;j>=0;j--)
{
sum=sum+arr[j];
if(sum>leftsum)
{
leftsum=sum;
maxleft=j;
}
}

rightsum=-10000000;
sum=0;
for(j=mid+1;j<=high;j++)
{
sum=sum+arr[j];
if(sum>rightsum)
{
rightsum=sum;
maxright=j;
}
}
a.lindex=maxleft;
a.rindex=maxright;
a.sum=leftsum+rightsum;
return(a);
}``````

Name:

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

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

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