public int maxSubArray(int[] A) {
    	if(A == null || A.length == 0) return 0;
		if(A.length == 1) return A[0];
		
		int max = 0, cur = 0, maxItem = A[0];
		for(int i = 0; i < A.length; i++){
			if(A[i] + cur >= 0) {
				cur += A[i];
				if(cur > max) max = cur;
			}
			else cur = 0;
            if(maxItem < A[i]) maxItem = A[i];
		}
		
        if(maxItem < 0) return maxItem;
		return max;
		
		// Slow version
//		int[] res = new int[A.length];
//		int max = A[0];
//		
//		for(int i = 0; i < A.length; i++){
//			res[i] = A[i];
//			if(A[i] > max) max = A[i];
//		}
//		for(int i = 1; i < A.length; i++){
//			for(int j = A.length - i - 1; j >= 0; j--){
//				res[j+i] = res[j+i-1] + A[j+i];
//				if(res[j+i] > max) max = res[j+i];
//			}
//		}
//		return max;
	}