問題タブ [kadanes-algorithm]

JavaでKadaneのアルゴリズムを次のように実装しています。基本的には、連続する部分配列の最大合計を見つけることです。

ただし、配列に負の数と正の数の組み合わせがある場合、これは機能しません。たとえば、次のようになります。

最大値として 12 を返す必要があります。今のところ5を返します

上記のコードは、最大サブ配列の合計を返します。

代わりに、合計が最大のサブ配列を返すにはどうすればよいですか？

Kadane のアルゴリズムを関数型スタイルでScala に実装した人はいますか?

編集注:リンクの定義は、この質問への回答を無効にする方法で変更されました。これは、外部リンクに依存するのではなく、質問 (および回答) を自己完結型にする必要がある理由を示しています。元の定義は次のとおりです。

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

配列の最大サブ配列の問題を解決するために、Kadaneのアルゴリズムを次のように実装しています。

の代わりにの-1, 2, 3結果を与えるように、負の数で始まるシーケンスを使用すると失敗します。4, [0,2]5, [1,2]

エラーがどこにあるのかわからない私の人生のために。多分それはアルゴリズム設計の欠陥ですか？

前もって感謝します。

その配列がある場合、最大のサブ配列を見つけるためのKadaneアルゴリズムの実装は機能します。

ただし、すべてのネガの配列がある場合：

動作しません。-10を返すはずですが、0になります。

どうすれば負の数でも機能させることができますか？

ありがとうございました！

次の問題を解決しようとしていました。

加重和問題

私が以前に行った最も近い問題は Kadane のアルゴリズムであるため、「ここで終わる最大」アプローチを試みた結果、次の DP ベースのプログラムが作成されました。アイデアは、問題をより小さな同一の問題 (通常の DP) に分割することです。

しかし、このプログラムは指定された制限時間内に動作しません (スペース制限は問題ありません)。この問題で使用するアルゴリズムのヒントを教えてください。

編集。

コードの説明は次のとおりです: Kadane の場合と同様に、私のアイデアは、特定の C[i] を調べ、次に C[i] で終わる m サブシーケンスの最大加重合計を取り、最後にすべての最大値を取ることです。すべての i にわたるそのような値。これで答えが得られます。ここで、C[i] で終わる m サブシーケンスを見て、最大加重合計を取る場合、これは C[0] に含まれる (m-1) サブシーケンスの最大加重合計を取るのと同じであることに注意してください。 C[i-1]に。そして、これは元の問題と同じ小さな問題です。そこで、再帰を使用します。関数の二重呼び出しを避けるために、値 f[i][j] のテーブルを作成します。ここで、f[ii][j] は、n を i に置き換え、m を に置き換えた問題と同じ問題の答えです。 j. つまり、f[i][j] のテーブルを作成し、最終的な答えは f[n-1][m] です (つまり、メモ化を使用します)。ここで、エントリ f[i][j] を計算するには前の列のみが必要であることに注意してください。配列のみを保持するだけで十分です。これらの配列は「a」と「b」です。

長くなってすみません、仕方ありません。:(

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

線形配列の場合、連続した番号の最大合計を見つける問題。は簡単だ。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まで

(n log n) を示すアルゴリズムを使用して、最大サブ配列問題を実装したいと考えています。

最大連続サブ配列、または配列内の連続要素の最大合計を見つけます。

仮定:すべての要素が負の数ではない

私はいくぶん実用的な解決策を持っています。問題は、重なっている中央の配列と、重なっているサブの問題を指定する適切なインデックスにあり、一部の配列は他の配列で正しい答えを得ていません。

比較と正確さの確認のために、Kadane のアルゴリズムとして知られるソリューションを実装しました (複雑さは Omega(n) だと思います)。

これはKandaneのアルゴリズムです(http://en.wikipedia.org/wiki/Maximum_subarray_problem):

分割と征服を使用してサブ配列の最大値を比較し、再帰が終了するまで、最大値を持つサブ配列で再帰呼び出しを行う私の再帰的実装

結果: 配列 subArrayProblem1 を使用 = {1, 2, 3, 4, 5, 6, 7, 8};

Kadane(int array []): 36 low: 0 mid: 4 1,2,3,4,5,6,7,8,mid: 4 high: 7 lowCenter: 6 highCenter: 6

findMaxSubArray(int[] array, int lowIndex, int highIndex) global Max Range, low:7 high: 7 global Max Sum:36 BUILD SUCCESSFUL (合計時間: 0 秒)

Kadane と比較するとグローバルな最大合計は正確ですが、低インデックスと高インデックスの範囲は最後の再帰呼び出しを反映しています。

結果: 配列 subArrayProblem を使用 = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};

Kadane(int array []): 1607 low: 0 mid: 8 100,113,110,85,105,102,86,63,mid+1: 9 high: 16 101,94,106,101,79,94,90,97,lowCenter: 16 highCenter: 15

findMaxSubArray(int[] array, int lowIndex, int highIndex) グローバル最大範囲、低:16 高: 16 グローバル最大合計:1526

グローバル最大値が正しくありません。違いは実際には 1 要素であり、要素 81 であることに注意してください

サブ配列には、正と負の両方の数値が含まれています。サブ配列の長さが k 以上になるような最大合計サブ配列を見つける必要があります。

Kadane のアルゴリズムを使用した C++ のコードを次に示します。

私のコードは正常に動作していますが、非常に遅く、コードを改善する方法が思い浮かびません。私はこの質問も読みました 合計がKで割り切れる最長の部分配列を見つけますが、それは私が望むものではありません。長さはkよりも大きくなる可能性があります。