問題タブ [kadanes-algorithm]

以下は、codility というコーディング インタビュー サイトからのデモの質問です。

文字列 S の接頭辞は、S の先頭の連続部分です。たとえば、「c」と「cod」は、文字列「codility」の接頭辞です。簡単にするために、プレフィックスは空ではない必要があります。

文字列 S のプレフィックス P の積は、P の出現回数に P の長さを掛けたものです。より正確には、プレフィックス P が K 文字で構成され、P が S 内でちょうど T 回出現する場合、積は K * T に等しくなります。

たとえば、S = "abababa" には次の接頭辞があります。

• 「a」、その積は 1 * 4 = 4 に等しい、
• 「ab」、その積は 2 * 3 = 6 に等しい、
• 「aba」、その積は 3 * 3 = 9 に等しく、
• 「abab」、その積は 4 * 2 = 8 に等しい、
• その積が 5 * 2 = 10 に等しい「アババ」、
• 「ababab」、その積は 6 * 1 = 6 に等しく、
• 「アババ」、その積は 7 * 1 = 7 です。

最長のプレフィックスは元の文字列と同じです。目標は、製品の価値を最大化するような接頭辞を選択することです。上記の例では、最大積は 10 です。

以下は、O（N ^ 2）時間を必要とするJavaでの私の貧弱なソリューションです。O(N)でこれを行うことは明らかに可能です。Kadanesアルゴリズムを考えていました。しかし、実行中の最大値を見つけることができるように、各ステップでいくつかの情報をエンコードできる方法は考えられません。このための O(N) アルゴリズムを考えられる人はいますか?

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

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

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

だから私はHackerRankの動的プログラミング トラックを通過しようとしています。

問題のプロンプトは次のとおりです。

N 要素の配列 A={a1,a2,…,aN} が与えられた場合、a の可能な最大合計を見つけます。

連続した部分配列 非連続 (必ずしも連続しているとは限らない) 部分配列。空のサブアレイ/サブシーケンスは考慮しないでください。

入力フォーマット

入力の最初の行には整数Tがあります。Tケースが続きます。各テスト ケースは、整数Nで始まります。次の行では、配列Aの要素を表すN 個の整数が続きます。

制約:

考慮するサブ配列とサブシーケンスには、少なくとも 1 つの要素が必要です。

出力フォーマット

2 つの、スペースで区切られた、最大連続部分配列および非連続部分配列を示す整数。少なくとも 1 つの整数を選択してサブ配列に入れる必要があります (これは、すべての要素が負の場合に必要になる場合があります)。

サンプル入力

サンプル出力

説明
最初のケース: 隣接する要素と隣接しない要素の両方の最大合計は、すべての要素の合計です (それらはすべて正であるため)。

2 番目のケース: [2 -1 2 3 4] --> これにより、合計が最大の連続したサブ配列が形成されます。必ずしも隣接していない要素のグループの最大合計については、単純にすべての正の要素を追加します。

したがって、上記のコードは 1 つのテスト ケースを除くすべてに合格します。これは非常に大きいので、すべてのテストケースを単体テストにアップロードし、ローカル環境で実行して何が起こっているかを確認することにしました。

これ

dp 関数が吐き出す連続していない回答に関して、2 桁が正しくありません。これは int から文字列への変換の問題でしょうか?

ユニコードと python 文字列を比較していることに気づきましたが、逆に試してみたので問題ないようですので、それが問題だとは思いませんが、間違っている可能性があります。

Python 2 で既知の境界を持つ 2D 配列の Kadane アルゴリズムを実装しましたが、その実装をオンライン コンテストに使用していて、指定された時間よりも時間がかかります。

そのため、Kadane のアルゴリズムに似た複雑さの少ない別のアルゴリズムがあるかどうか、または私のコードを何らかの方法で最適化できるかどうかを考えさせられました。私の実装は、次元 x の任意の配列と次元NxMのサブ配列maxRowsに対して機能しmaxColsます。

maxSumSubarray.py

test.txt

で実行

それは与えます

これは正しく、次の長方形です。

私は他の次元でも試しましたが、うまくいくと確信しています。唯一の問題は時間/複雑さです。どんな助けでも大歓迎です！御時間ありがとうございます。

最良の開始インデックスを更新したい 配列 A={-1,-2,5,0,1} がある場合 最良の開始はインデックス 2 であり、最良の終了インデックスは 4 である必要があります 最良の終了を取得していますが、わかりませんここで最高の開始最大サブ配列を更新する方法は = 6 (5+0+1) です

Prolog でKadane のアルゴリズムを実装しようとしています。要件の 1 つは末尾呼び出し (再帰) です。

私は多くの可能性を試しましたが、成功しませんでした。これが私のコードです：

NewH、NewS は一時的な値です (Prolog で値を 2 回割り当てることはできませんよね?)。ヒントをお願いできますか？

編集：

Call(11) では、この単純な例から良い結果 (6) が得られました。この時点で、戻らずに関数を終了するにはどうすればよいですか? それは私の問題です。

このコードの結果は、S = 6 ではなく、S = 0 です。

最終編集 (作業コード):

どこ：

• S - 最終結果、
• F - maximum_so_far、
• H - maximum_ending_here,
• X - リストの先頭、
• L - リスト、
• NewH、NewF - 一時値。

助けてくれてありがとう ：）

連続する配列の合計の最大値 (負の数を含む) を見つけようとしました。私が間違っている単一のケースを見つけるのを手伝ってください。

たとえば、

負の数と追加の変数 k があるため、これはさらに注意が必要です。k は任意の値、負の値にすることができます。仮定はしないでください。

この問題を解決するためにhttps://en.wikipedia.org/wiki/Maximum_subarray_problemとhttps://www.youtube.com/watch?v=yCQN096CwWMを参照できません。

どんな体でも私を助けることができますか？Java または JavaScript を使用することをお勧めします。

最大値 (変数 k なし) の古典的なアルゴリズム o(n) は次のとおりです。

javascriptで効率的にさらに計算するために、すべてのサブ配列を収集したいと考えています。これが可能かどうかはわかりませんが、部分配列の合計 kadane の式は o(n) であり、他の方法よりも効率的です。しかし、各ステップで配列を保存する方法がわかりません。

このquora questionと同様に、私にとって疑似コードは十分ではありませんでした。さらなる内訳をありがとう。

別のメタリンク

[3, 3, 9, 9, 5] に対するこれの実行例