Interview Questions

202. Given an array (can have negative numbers). .......

Microsoft Interview Questions and Answers


(Continued from previous question...)

202. Given an array (can have negative numbers). .......

Question:
Given an array (can have negative numbers), find the sub-array with maximum sum. Follow-up question. Find the sub-array with minimum sum.


maybe an answer:


public static void main(String[] args) {
int arr [] = {1,2,3,-5,-3,2,7,-4,5};
int maxSoFar [] = new int [3]; //holds i,j and maxvalue in 0,1 and 2 positions
int maxEndHere [] = new int [3]; //holds i,j and maxvalue in 0,1 and 2 positions
boolean flag = false;
for (int i = 0; i < arr.length; i++) {
int max = Math.max(0,maxEndHere[2]+arr[i]);
if(max>0){
if(!flag){
maxEndHere [0] = i;
maxEndHere [1] = i;
maxEndHere [2] = arr[i];
flag = true;
}else{
maxEndHere [1] = i;
maxEndHere [2] += arr[i];
}
}else{
flag = false;
}
if(maxSoFar[2] maxSoFar [0] = maxEndHere [0];
maxSoFar [1] = maxEndHere [1];
maxSoFar [2] = maxEndHere [2];
}

}
for (int i = maxSoFar[0]; i <= maxSoFar[1]; i++)
System.out.println(arr[i]+" ");
}

(Continued on next question...)

Other Interview Questions