Interview Question
Country: United States
Complexity O ( N )
public static void findMaxSubArray(int[] A){
int start = 0;
int end = 0;
int start_so_far = 0;
int max = 0;
int max_so_far = 0;
for( int i = 0; i < A.length; i++)
{
max_so_far += A[i];
if( max_so_far >= max ){
max = max_so_far;
end = i;
start = start_so_far;
}else if(max_so_far < 0){
max_so_far = 0;
start_so_far = i + 1;
}
}
for(int i= start; i <= end; i++){
System.out.print(A[i] + " , ");
}
System.out.print(" = " + max);
}
use kadane's algorithm
- anon123 February 17, 2014