1

数日前に終了した割り当てを調べていて、定数を使用することになっていないことに気付きました。この割り当ては、よく知られている「分割統治法を使用して、正と負の両方の整数のサブ配列の最大合計を再帰的に見つける」問題です。私のアルゴリズムは機能しますが、その一部は、配列の中央を含むサブ配列の最大の合計を計算するために定数を使用します。

関連するコードは次のとおりです。

lfSum = Integer.MIN_VALUE;
sum = 0;
// Sum from left to mid
for (int i = mid; i >= LF; i--) {
    sum += array[i];
    if (sum > lfSum) {
        lfSum = sum;
        if (lfSum > lfMax) {
            lfMax = lfSum;
        }
    }
}

rtSum = Integer.MIN_VALUE;
sum = 0;
// Sum from mid to right
for (int j = mid+1; j <= RT; j++) {
    sum += array[j];
    if (sum > rtSum) {
        rtSum = sum;
        if (rtSum > rtMax) {
            rtMax = rtSum;
        }
    }
}

// Largest sum spanning whole array
midMax = lfSum + rtSum; // midMax = leftMid + midRight;

これは、配列全体の各半分をループし、配列全体が負の場合に合計が可能な最小の整数よりも大きいかどうかを確認します。そうである場合は、その側の最大合計を合計の値に設定します。その値が再帰呼び出しの1つが返した値(lfMaxまたはrtMax)よりも大きい場合は、それぞれの側の再帰値をそれに設定します。

前に言ったように、これは完全にうまく機能しますが、「Integer.MIN_VALUE」を使用することは想定されていません。これを回避する別の方法はありますか?もちろん、lfSum / rtSumをInteger.MIN_VALUEの数値に初期化することはできますが、他にオプションがあるかどうかを知りたいです。

rtSum / lfSumを削除し、合計を再帰値と比較し、lfSum / rtSumを0に初期化しようとしましたが、両方とも正しく機能しませんでした。これを読んでくれてありがとう!

4

1 に答える 1

1

lfSum次のように初期化できますnull

Integer lfSum = null;

そして、次のようにif条件を変更します。

if (lfSum == null || (lfSum != null && sum > lfSum.intValue())) {
    lfSum = sum;
    if (lfSum > lfMax) {
        lfMax = lfSum;
    }
}

同様の戦略がに適用されrtSumます。

于 2013-03-03T22:33:20.153 に答える