public static int findMaxSub(int[] A, int left, int right, int maxSum) {
        if (left > right) return Integer.MIN_VALUE;//wrong parameters
        int mid = (left + right) / 2;
        int leftmax = findMaxEntirelyInLeftRight(A, left, mid);//max sub array entirely in left
        int rightmax = findMaxEntirelyInLeftRight(A, mid, right);//max sub array entirely in right
        int max = Math.max(leftmax, rightmax);
        //left
        int sum = 0, midLeftMax = 0;
        for(int i = mid - 1; i >= left; i--) {
            sum += A[i];
            if(sum > midLeftMax) midLeftMax = sum;
            //note: sum is not zeroed even if it is minus 0, since this
            //subsequence must be continuous with A[mid];
        }
        //right
        sum = 0;
        int midRightMax = 0;
        for(int i = mid + 1; i <= right; i++) {
            sum += A[i];
            if(sum > midRightMax) midRightMax = sum;
        }
        // get the max value from the left, right and across mid
        return Math.max(max, midLeftMax + midRightMax + A[mid]);
    }