0

最大部分列合計プログラムの再帰的解法に基づいた最大部分列積プログラムを作成しようとしています (つまり、同じ形式に従います)。

これまでのところ、結果が「0」になる場合を除いてすべてのケースで機能し、シーケンス内に正の製品がないことを示します。以下の 5 つのシーケンスでは、最後のシーケンスを除くすべてのシーケンスで機能します。

sequence1 = new int[]{-2, 5, 4, 4};
sequence2 = new int[]{6, 5, 0, -3, -5, -3, 7};
sequence3 = new int[]{0, -1, 1, 5, 0, -3, -4};
sequence4 = new int[]{0, 3, 3};
sequence5 = new int[]{0, -3, 3};

a はシーケンス、p1 は最初は a[0]、p2 は a[最後のインデックス] です。

public static int msp3(int[] a, int p1, int p2) {

    if (p1 == p2) {
        if (a[p1] != 0) {
            maxprod = a[p1];
        } else {
            maxprod = 0;
        }

    } else {
        int m = (p1 + p2) / 2;

        int L = msp3(a, p1, m);
        int R = msp3(a, m + 1, p2);

        int prodlt = 1, prodrt = 1, PL = 0, PR = 0;

        int checkForSplit = 0;

        for (int i = m; i >= p1; i--) {

            if (a[i] != 0) {
                prodlt = prodlt * a[i];

                if (prodlt > PL) {
                    PL = prodlt;
                }
            } else {
                if (i == m) {
                    prodlt = 1;
                    checkForSplit = 1;
                }
            }
        }

        for (int i = m + 1; i <= p2; i++) {
            if (a[i] != 0) {
                prodrt = prodrt * a[i];

                if (prodrt > PR) {
                    PR = prodrt;
                }
            } else {
                if (i == m + 1) {
                    prodrt = 1;
                    checkForSplit = 1;
                }
            }
        }

        if (checkForSplit == 0) {
            maxprod = max3(L, R, PL * PR);
        } else {
            maxprod = max3(L, R, PL);
            maxprod = max(maxprod, PR);
        }

    }
    return maxprod;
}

'checkForSplit' に関する注意。a[i] == 0 でない限り、値は 0 です。現在のサブシーケンスの左端または右端のインデックスをチェックしています。この場合、1 に設定されます。これにより、' の別の計算がトリガーされます。 max3' ここで、PL は PR で乗算されません。ロジックは、PL または PR のいずれかが 0 の場合、2 つのうちの他方がそうでない可能性があり、その場合、それらを乗算するべきではないということです。

前述したように、このアルゴリズムは 5 番目のシーケンスを除くすべてのシーケンスで機能します。

何か案は？

4

1 に答える 1