algorithm - 最大和/面積部分行列

Question

入力: 正/負の数と k の nxn 行列。

出力: 要素の最大合計を少なくとも k 個の要素を持つ要素の数で割った部分行列。

この問題に対して O(n^4) よりも優れたアルゴリズムはありますか?

Answer 1

nxn 行列の最大和部分行列 (つまり、subrectangle) を見つけるための O(n^3) 2-d kadane アルゴリズムがあります。(SO に関する投稿を見つけるか、オンラインで読むことができます)。アルゴリズムがどのように機能するかを理解したら、1 次元配列で少なくとも m の長さの最大平均サブインターバルを見つける問題を解決できれば、問題の O(n^3) 時間の解を得ることができることは明らかです。 O（n）時間でn個の数。これは確かに可能です。論文 cs.slu.edu/~goldwasser/publications/DensityPreprint.pdf を参照してください。

したがって、問題には O(n^3) 時間の解決策があります。