2

整数の特定の入力配列に対して、値が重複する可能性のある、空ではない連続したサブ配列を見つけたいと思います。分割統治法を試して、配列の最大連続サブ配列を見つけました。これにより、期待どおりに異なる結果が返されます。以下のコードを見つけてください。

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);
}

このコードは、結果を2000005400として返します。非再帰バージョンのMCSは、異なる結果、つまり2000010721とその{1-94}からの結果を返します。理由がわかりません。コードにバグがある場合はお知らせください。

4

2 に答える 2

3

1から95までの合計（：4000010711）は、実際には1から94までの合計よりも大きくなります。

あなたintsは長すぎます。

long正しい結果を得るにはを使用する必要があります。

ノート：

intは-2147483648と2147483647の間です

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

あなたが得るでしょう：

2147483647
-2147483648

これを試して ：

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));
        }


}

あなたが得るでしょう：

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
于 2011-08-09T13:48:23.757 に答える
0

コメントを追加するのに十分なポイントがないため、簡単なコメントの回答を作成しました。

リッキーの答えはほとんどの場合機能しますが、[-2、-1]などの配列の場合は機能しません。単に追加します：

leftSum = a [mid]; rightSum = a [mid + 1];

あなたがそれらを使う前にどこかでそしてそれはトリックをするでしょう。

于 2012-12-27T21:47:42.103 に答える