問題タブ [kadanes-algorithm]

最大サブアレイ問題によく似た問題を解決する必要があります。平均が k より大きい最大の部分配列を見つけなければなりません。次のトリックを考えました。サイズ n の配列 A[] を B[i] = A[i] - k の B[] に変換できます。したがって、平均は >0 でなければなりません。しかし、ゼロより大きい平均は、単純に合計がゼロより大きいという意味ではありませんか? したがって、Kadane のアルゴリズムを直接適用できます。私は正しいですか？(常に 1 つの正の値があるという制約の下で)

上記のアルゴリズムで、最適なサブ構造とオーバーラップの問題(DPのパンとバター)を理解するのを手伝ってくれる人はいますか?

Kadane のアルゴリズム ( http://en.wikipedia.org/wiki/Maximum_subarray_problem ) を使用して、数値の 1 次元配列内の連続する部分配列の最大合計を見つけます。

では、これをどのように使用して、同じ最大和を持つシーケンスの数を見つけるのでしょうか? そのようなシーケンスをカウントするためにアルゴリズムにどのような変更を加えることができますか..

例：

Kadane の 2D Matrix アルゴリズムの C# コードを実装する方法を理解しようとしています。ここで1Dバージョンを見つけました：

最大合計で部分配列を見つける Kadane のアルゴリズム

でも2D版が欲しい。基本的に、正と負の数の行列 N x N が与えられた場合、すべての要素の合計が最大になる部分行列を見つける必要があります。

N 個のゼロ以外のエントリを持つスパースな mxn 行列があります。
の修正版は、十分にスパースな行列の従来の Kadane のアルゴリズムを打ち負かすKadane's 2-d algorithm、時間内の最大和部分四角形を見つけることができます。 ここで、マトリックスの 1 つのエントリが変更された場合に、最適なソリューションをすばやく更新できるかどうかを知りたいと考えています。 「すぐに」とは、次のような意味です。 おそらく、行列がスパースでなくてもうまくいく可能性があります。O(m N log n)O(m^2 n)

O(m log n) time or better
a solution, however a solution when N = O(min(m,n)) would be ok

subarray の最小スライスに関するコードの質問に対する解決策を見つけようとしています。Kadaneのアルゴリズムの修正版を使用して解決策を考案しました。私は現在、90/100 を取得しており、O(n) のほぼすべてのテストに合格することができました。ただし、「medium_range、増加、減少 (レグス = ~100)、および小さな機能、期待される 5 の 3」を渡すことができないようで、その理由がわかりません。これはおそらく解決策の繰り返しですが、私は少し異なる解決方法を使用しています。

私の論理は次のとおりです。

a) 配列 MinA がある場合、MinA[k] は k から始まり、最小長が 2 の部分配列の最小平均スライスを表します。

b) 次に、MinA をループして配列の最小値を見つけると、これが配列全体の最小平均スライスになります (そして、インデックス位置を返します)

c) この MinA を作成するには、配列の最後から 2 番目の要素から開始し、MinA[A.length -2] は A の最後の 2 つの要素の平均です。

d) カウンターを 1 ポジション左に移動します。MinA[カウンター] は、A[カウンター] と A[カウンター + 1] の平均、または要素カウンターと MinA[カウンター + 1] 内の要素の平均のいずれかでなければなりません。

e) d が真でない場合、これは、MinA[カウンター + 1] が、カウンター + 1 からカウンター + 2 から N までの何らかの要素までの最小平均スライスではないことを意味します。

私は何かが足りないのだろうか？

ここで与えられた実装が正しいかどうか懐疑的だったので、正確に C++ で実装しましたが、上記のテスト ケースでは機能しません。アルゴリズムのどこが間違っているのかわかりませんか?