public static int kadanesAlgorithm(int[] array) {
   
int maxEndingHere = array[0];
int maxSoFar = array[0];
		
for(int i=1; i<array.length; i++){
			
maxEndingHere = Math.max(maxEndingHere+ array[i], array[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
			
}
return maxSoFar;
}