Search code examples
javaalgorithmdivide-and-conquersub-array

Problem with Divide and Conquer Maximum Consecutive Subarray (MCS)


I want to find a nonempty, contiguous subarray for a given input array of integers, that can have duplicate values. I tried the divide and conquer method to find the maximum consecutive subarray of an array, which returns a different result as expected. Please find the code below.

private static int maxSumRec(int[] a, int low, int high) {
    int leftSum = 0, rightSum = 0;
    int sum = 0; 

    if (low == high) { // Base case
        return a[low]; 
    }

    int mid = (low + high) >> 1; // (low + high) / 2
    int maxLeftSum = maxSumRec(a, low, mid);
    int maxRightSum = maxSumRec(a, mid + 1, high);

    //max-crossing-subarray
    for (int i = mid; i >= low; i--) {
        sum += a[i];
        if (sum > leftSum) {
            leftSum = sum;
        }
    }
    sum = 0;
    for (int i = mid + 1; i <= high; i++) {
        sum += a[i];
        if (sum > rightSum) {
            rightSum = sum;
        }
    }
    return max3(maxLeftSum, maxRightSum, (leftSum + rightSum));
}

private static int max3(int a, int b, int c) {
    return a > b ? (a > c ? a : c) : (b > c ? b : c);
}

public static void main(String[] args) {


    //INPUT
    int a[] = {
        -5, 71, 23, 41, 34, 1, 3, 6, 2, 91, 312, 42, 31, 67, 12, 10, 18, 56, 90, 21, 45, 47, 89, 1999999990,
        78, -7, 76, 75, 74, 73, 72, 80, 24, 25, 61, 69, 84, 0, -1, 145, 1902, 200, 199, 198, 197, 196, 195, 194,
        78, 77, 76, 75, 74, 73, 72, 80, 24, 25, 61, 69, 84, 0, -1, 145, 1902, 200, 199, 198, 197, 196, 195, 194,
        5, 71, 23, 41, 34, 1, 3, 6, 2, 91, 312, 42, 31, 67, 12, 10, 18, 56, 90, 21, 45, 47, 89, 1999999990
    };

    int maxSum = maxSumRec(a, 0, a.length - 1);
    System.out.println("Max sum is " + maxSum);
}

This code returns the result as 2000005400. The non recursive version of MCS returns a different result i.e. 2000010721 and its found from {1-94}. I'm unable to figure out the reason. Please let me know if there's a bug in the code.


Solution

  • The sum from 1 to 95 (it's :4000010711 ) is actually greater than the one from 1 to 94.

    Your ints are too long.

    You need to use long to get the right result.

    Note:

    int are between -2147483648 and 2147483647

    int test=2147483647;
    System.out.println(test);
    System.out.println(test+1);
    

    you will get:

    2147483647
    -2147483648
    

    Try this :

    public class Sample5 {
            private static long maxSumRec(int[] a, int low, int high) {
                long  leftSum = 0, rightSum = 0;
                long  sum = 0; 
    
                if (low == high) { // Base case
                    return a[low]; 
                }
    
                int mid = (low + high)/2; // (low + high) / 2
                long maxLeftSum = maxSumRec(a, low, mid);
                long maxRightSum = maxSumRec(a, mid + 1, high);
    
                //max-crossing-subarray
                for (int i = mid; i >= low; i--) {
                    sum += a[i];
                    if (sum > leftSum) {
                        leftSum = sum;
                    }
                }
                sum = 0;
                for (int i = mid + 1; i <= high; i++) {
                    sum += a[i];
                    if (sum > rightSum) {
                        rightSum = sum;
                    }
                }
                System.out.println("final left sum "+leftSum);
                System.out.println("final right sum "+rightSum);
                System.out.println("leftSum+rightSUM:"+(leftSum + rightSum));
                return max3(maxLeftSum, maxRightSum, (leftSum + rightSum));
            }
    
            private static long max3(long a, long b, long c) {
                return a > b ? (a > c ? a : c) : (b > c ? b : c);
            }
    
            private static int sum(int[] a,int i,int j){
                int r=0;
                for(int k=i;k<=j;k++){
                    r+=a[k];
                }
                return r;
            }
            public static void main(String[] args) {
    
    
                //INPUT
                int a[] = {
                    -5, 71, 23, 41, 34, 1, 3, 6, 2, 91, 312, 42, 31, 67, 12, 10, 18, 56, 90, 21, 45, 47, 89, 1999999990,
                    78, -7, 76, 75, 74, 73, 72, 80, 24, 25, 61, 69, 84, 0, -1, 145, 1902, 200, 199, 198, 197, 196, 195, 194,
                    78, 77, 76, 75, 74, 73, 72, 80, 24, 25, 61, 69, 84, 0, -1, 145, 1902, 200, 199, 198, 197, 196, 195, 194,
                    5, 71, 23, 41, 34, 1, 3, 6, 2, 91, 312, 42, 31, 67, 12, 10, 18, 56, 90, 21, 45, 47, 89, 1999999990
                };
    
                long maxSum = maxSumRec(a, 0, a.length-1);
                System.out.println("Max sum is " + maxSum);
    
                //WITH INTS
                System.out.println("with ints, the sum 1 to 94 is " + sum(a,1,94));
                System.out.println("with ints, the sum 1 to 95 is " + sum(a,1,95));
            }
    
    
    }
    

    You will get :

    final left sum 2000005311
    final right sum 2000005400
    leftSum+rightSUM:4000010711
    Max sum is 4000010711
    with ints, the sum 1 to 94 is 2000010721
    with ints, the sum 1 to 95 is -294956585