public int maxSubArray(int[] A) {// O(n) space

		if (A == null)
			return 0;

		int[] buffer = new int[A.length];
		buffer[0] = A[0];
		int max = buffer[0];

		for (int i = 1; i < A.length; i++) {
			buffer[i] = Math.max(A[i], buffer[i - 1] + A[i]);
			max = Math.max(buffer[i], max); // keep track of the largest sum
		}
		return max;
	}