Kadane's Algorithm Variant (Start Index and End Index with Sub Array returned even for all negative numbers)

Question

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);
 }
 }
}

Answer 1

Bug

The first condition maxSoFar < array[i] is wrong and should be removed. Otherwise a sequence such as 5 -10 6 will not find 6 as the max sum.

Complicated expression

The other condition:

 if (array[i] >= maxEndingHere + array[i]) {

is overly complicated. If you subtract array[i] from both sides, you can simplify to:

 if (maxEndingHere <= 0) {

Answer 2

It will fail in the case 8, -19, 5, -4, 20. The startIndex and endIndex will not update until 20, but the start should be 5.