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
|