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