@@ -0,0 +1,1932 @@
+package arrays.maximum_sub_array;%0Aimport arrays.maximum_sub_array.SubArray;%09// My implementation of class SubArray to hold result sub array%0A%0A/*%0AThis class implements Kadane's algorithm to find the maximum sum sub array in a given array.%0A*/%0A%0Aclass MaximumSubArray%7B%0A%0A%09// Finds maximum sum sub array and returns SubArray object%0A%09// Returns null if array A is null or of length 0%0A%0A%09public static SubArray find(int%5B%5D A)%7B%0A%0A%09%09// Return null if array is null or empty%0A%09%09if(A == null %7C%7C A.length %3C 1)%0A%09%09%09return null;%09%0A%0A%09%09SubArray endHere = new SubArray(); %09%09// Holds maximum sum sub array ending at current index while traversing input array%0A%09%09SubArray soFar = new SubArray();%09%09// Holds maximum sum sub array encountered so far.%0A%0A%09%09// Set ending here and so far sub arrays to be the first element of the input array%0A%09%09endHere.setStart(0);%0A%09%09endHere.setEnd(0);%0A%09%09endHere.setSum(A%5B0%5D);%0A%0A%09%09soFar.setStart(0);%0A%09%09soFar.setEnd(0);%0A%09%09soFar.setSum(A%5B0%5D);%0A%0A%0A%09%09// for each element from index 1 to A.length -1%0A%09%09for(int i=1;i%3CA.length;i++)%7B%0A%0A%09%09%09// If sum ending at previous index (i-1) was positive%0A%09%09%09if(endHere.getSum() %3E 0)%7B%0A%0A%09%09%09%09// set sum ending at current index (i) as previous sum + value at current index%0A%09%09%09%09endHere.setSum(endHere.getSum() + A%5Bi%5D);%0A%0A%09%09%09%09// Update end index to i %0A%09%09%09%09endHere.setEnd(i);%0A%09%09%09%7D%0A%09%09%09else%7B%0A%09%0A%09%09%09%09// Otherwise, set sum ending at current index as value at current index%0A%09%09%09%09endHere.setSum(A%5Bi%5D);%0A%09%09%09%09%0A%09%09%09%09// Set start and end index as i%0A%09%09%09%09endHere.setEnd(i);%0A%09%09%09%09endHere.setStart(i);%0A%0A%09%09%09%7D%0A%0A%09%09%09// If sum ending at current index is greater than sum encountered until previous index (sofar), %0A%09%09%09// set sum encountered so far to the current sum, and update start and end indices%09%0A%09%09%09%0A%09%09%09if(endHere.getSum() %3E soFar.getSum())%7B%0A%0A%09%09%09%09soFar.setSum(endHere.getSum());%0A%09%09%09%09soFar.setEnd(endHere.getEnd());%0A%09%09%09%09soFar.setStart(endHere.getStart());%0A%09%09%09%7D%0A%0A%09%09%09%0A%09%09%7D%0A%0A%09%09// Return maximum sub array encoutered %0A%09%09return soFar;%0A%0A%09%7D%0A%0A%0A%7D

Add Kadane's algorithm