19

Kadane のアルゴリズムで何が起こっているのか、誰か教えてくれませんか? 私の理解を確認したかった。これが私がそれを見る方法です。

配列をループし、ans 変数を表示される最大値に設定するたびに、その値が負になるまで、ans はゼロになります。

同時に、sum 変数はループのたびに上書きされ、以前に見られた合計の最大値またはこれまでの最大の「ans」まで上書きされます。ループの実行が終了すると、これまでに見た最大の合計または答えが得られます!

var sumArray = function(array) {
      var ans = 0;
      var sum = 0;
      //loop through the array.


      for (var i = 0; i < array.length; i++) {
        //this is to make sure that the sum is not negative. 
        ans = Math.max(0, ans + array[i]);

        //set the sum to be overwritten if something greater appears.
        sum = Math.max(sum, ans)
      }

      return sum;

    };
4

6 に答える 6

19

値をトレースすることを検討してください。

var maximumSubArray = function(array) {
    var ans = 0;
    var sum = 0;

    console.log(ans, sum);
    for (var i = 0; i < array.length; i++) {

        ans = Math.max(0, ans + array[i]);
        sum = Math.max(sum, ans);
        console.log(ans, sum, array[i]);
    }
    console.log(ans, sum);
    return sum;

};

maximumSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]);

版画:

0 0
0 0 -2
1 1 1
0 1 -3
4 4 4
3 4 -1
5 5 2
6 6 1
1 6 -5
5 6 4
5 6

最初の列はansで、これは現在の部分配列の合計です。2 番目はsumで、これまでに見られた最大のものの合計を表します。3 番目は、ちょうど訪問された要素です。4, −1, 2, 1合計が最大の連続する部分配列は で、合計は であることがわかります6。

例はウィキペディアからのものです。

以下は、ウィキペディアの段落の下にあるコードの翻訳です。次のコード:" [編集: 以下のコードで修正された小さなバグ]

var maximumSubArray = function(array) {
    var ans = array[0];
    var sum = array[0];

    console.log(ans, sum);
    for (var i = 1; i < array.length; i++) {

        ans = Math.max(array[i], ans + array[i]);
        sum = Math.max(sum, ans);
        console.log(ans, sum, array[i]);
    }
    console.log(ans, sum);
    return sum;

};

次のことを確認してください。

> maximumSubArray([-10, -11, -12])
-10 -10
-10 -10 -11
-10 -10 -12
-10 -10
-10

最後の数字は期待される結果です。その他は前の例のとおりです。

于 2015-09-03T04:57:11.143 に答える
4

このリンクを見てください。カダネのアルゴリズムについて明確な説明があります。

基本的に、配列のすべての正の連続セグメントを探し、連続セグメントの最大合計を最後まで追跡する必要があります。新しい正の連続セグメントが見つかると、現在の合計がmax_sumこれまでの合計よりも大きいかどうかがチェックされ、それに応じて更新されます。

次のコードは、すべての数値が負の場合を処理します。

int maxSubArray(int a[], int size)
{
   int max_so_far = a[0], i;
   int curr_max = a[0];

   for (i = 1; i < size; i++)
   {
        curr_max = max(a[i], curr_max+a[i]);
        max_so_far = max(max_so_far, curr_max);
   }
   return max_so_far;
}
于 2015-09-03T04:53:10.507 に答える