4

I Implemented the Kadane's Max Sub array problem in javascript but seems i end up always getting 0 in the console even though there exists higher numbers( I understand that it does what it's doing because of for loop from 0 - size where size = subarray size).

  • So how do i implement the algorithm correctly?

  • Does it also work for all positive integer array?

JsBin

http://jsbin.com/ajivan/edit#javascript,live

4

3 に答える 3

11

配列の長さが 6 のときに引数として n=3 を渡しています。使用するアルゴリズムを次のように変更しましたlength。

function SubSequence(a){
  var now = 0,prev =0;
  for(var i = 0;i < a.length;i++){  
    prev = Math.max(0,prev + a[i]);
    now = Math.max(prev,now);
  }
  return now;
}

console.log(SubSequence([-1,-2,-3,4,6,7]));

そしてそれは17を与えます。

すべての正の整数配列でも機能しますか?

はい、配列内のすべての要素の合計が得られます。

長さ 3 の最大サブシーケンスが必要な場合は、次を使用します。

function SubSequence(a,n){
  var now = 0;
  for(var i = 0; i < n; i++) {
    now += a[i];
  }
  var best = now;
  for(var i = n;i < a.length;i++) {
    now += a[i] - a[i-n];
    best = Math.max(now,best);
  }
  return best;
}

console.log(SubSequence([-1,-2,-3,4,6,7,1,4],3));

最適なのは 4+6+7 ですが、4+6+7+1+4 は許可されていません。

于 2012-06-07T05:36:48.940 に答える
1

コンピューター サイエンスでは、最大部分配列問題は、数値の 1 次元配列 (少なくとも 1 つの正の数を含む) 内で合計が最大になる連続した部分配列を見つけるタスクです。

Kadane のアルゴリズムは、上記の問題の解を求める方法です。

Kadane のアルゴリズムの単純なアイデアは、配列のすべての正の連続セグメントを探すことです (max_ending_here としましょう)。そして、すべての正のセグメントの中で連続するセグメントの最大合計を追跡します (max_so_far としましょう)。正の合計を取得するたびに、それを max_so_far と比較し、max_so_far より大きい場合は max_so_far を更新します。

アルゴリズムは、すべての負の数に対して機能するわけではありません。すべての数値が負の場合は、単に 0 を返します。これを処理するために、実際の実装の前に追加のフェーズを追加できます。フェーズは、すべての数値が負の場合に表示され、負の場合はそれらの最大値 (または絶対値の点で最小) が返されます。

あなたが投稿したのは、配列内のすべての数値が負の場合の実装です。実際のアルゴリズムではなく、余分なフェーズを参照しています。1 次元配列の Kadane アルゴリズム:

this is the general algorithm.
    Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

この説明がお役に立てば幸いです。

于 2013-10-16T10:17:23.137 に答える