public class MaxSubArrayUsingKadane {
	 int[] maxSubArray(int[] A) {
		if(A.length == 0) return null;

		int max = A[0], sum = A[0];
		int high = 0, low = 0;
		for(int i = 1; i < A.length; i++) {
			if(sum+A[i] <= A[i]) {
				sum = A[i];
				low = i;
				System.out.println(low);
			} else {
				sum = sum+A[i];
			}

			if(max <= sum) {
				max = sum;
				high = i;
			}
		}
		//This check is necessary when all inputs are less <= 0
		if(high < low) {
			low = high;
		}
		int[] ans = {low, high, max};
		return ans;
	}

}