Here is an attempt to extend the Kadane's Algorithm to return the sub array itself instead of the sum of maximum sub array. This must work irrespective of the original array having all positive or negative numbers.
public class MaxSubArray {
public static void main(String[] args) {
int array[] = {10, -9, 4, 5, 90, -19, 19}; // Max sum is 100
//int array[] = {4, -3, 6}; // Max Sum is 7
//int array[] = {-1, -2, -3}; // Max Sum is -1
//int array[] = {1, -2, -3}; // Max Sum is 1
//int array[] = {-4, -3, -6}; // Max Sum is -3
//int array[] = {-6, 0, 5}; // Max Sum is 5
//int array[] = {0, 0, 0}; // Max Sum is 0
int[] maxSubArray = getMaxSubArray(array);
System.out.println(Arrays.toString(maxSubArray));
}
// Kadane's Alorithm Variant (Start Index and End Index of Sub Array even for all negative numbers)
private static int[] getMaxSubArray(int[] array) {
if (array == null || array.length == 0) {
return array;
} else {
int startIndex = 0, endIndex = 0;
int maxSoFar = array[0], maxEndingHere = array[0];
for (int i = 1; i < array.length; i++) {
if(maxSoFar < array[i] && array[i] >= maxEndingHere + array[i]) {
maxEndingHere = array[i];
startIndex = i;
endIndex = i;
} else {
maxEndingHere += array[i];
}
if(maxEndingHere > maxSoFar) {
maxSoFar = maxEndingHere;
endIndex = i;
}
}
return Arrays.copyOfRange(array, startIndex, endIndex + 1);
}
}
}
