3

線形配列の場合、連続した番号の最大合計を見つける問題。は簡単だ。Kadane's Algoを使えば簡単にできます。. しかし今、配列は円の形をしており、連続する番号の最大合計を見つける必要があります。したがって、startindex と endindex は配列内のどこにでも置くことができます。時間内に解決する方法がわかりませんO(n)。

例: { 8, 9, -14, 4, 3}.

最大部分配列sum= 4+3+8+9= 24. startindex=3 and endindex=1(ゼロ インデックス配列)。この問題にアプローチする方法について、ヒントまたはアルゴリズムを教えてください。コードは必要ありません。

編集:誰もが述べたように、円形配列は2回スパンする同じ配列に似ています。しかし、その配列に Kadane の Algo を適用し、連続番号を制限する方法。<=nまで

4

3 に答える 3

3

取得するために配列を一度コピーし { 8, 9, -14, 4, 3, 8, 9, -14, 4, 3}、

長さが元の円を超えない最大の部分配列を見つけます。

于 2012-07-23T10:18:55.760 に答える
3

または、配列をコピーするのではなく、インデックス変数の範囲を から に拡張し、0..n-1代わりにインデックスとして0..2n-1使用します。(x mod n)x

于 2012-07-23T10:23:44.927 に答える
2
  1. Kadane のアルゴリズムによって最大和を求めるというコンセプトです。
  2. 次に、要素を否定することによってカダネのアルゴリズムによって最小合計を見つけ、これを配列の合計合計に追加します。

ステップ 1 とステップ 2 で計算された要素の最大値を出力します。

private static int maxCircularSum(int a[]) {
    int max_kadane = kadane(a);
    int max_wrap = 0, i;
    for (i = 0; i < a.length; i++) {
        max_wrap += a[i]; // Calculate array-sum
        a[i] = -a[i];  // invert the array (change sign)
    }
    max_wrap = max_wrap + kadane(a);
    return (max_wrap > max_kadane) ? max_wrap : max_kadane;
}
private static int kadane(int[] a) {
    int max = Integer.MIN_VALUE, sum = 0;
    for (int k : a) {
        sum = sum + k;
        if (sum < 0) {
            sum = 0;
        }
        if (max < sum) {
            max = sum;
        }
    }
    return max;
}
于 2013-10-04T01:34:19.047 に答える