行列内で最大の合計を持つ正方形

Question

私はかなり典型的な問題を抱えていると私は思います。私はここに似たトピックがあることを知っていますが、私は初心者であり、この問題のさまざまなバージョンを区別していないことを理解しています。時には、テキストやアルゴリズムにほとんど差が完全に異なる場合があります。..だから、問題は次のとおりです。

For a given 2<=a,b<=1000 and 1<=c<=Min(a,b) find in matrix a x b square c x c 
with the largest sum of elements. The elements in matrix are from -1000 to 1000. 

私は行列全体を実行し、すべての点（x、y）上で、それがために合計をカウントするアルゴリズムを書くことができます（x、y + c）、（x + c、y + c）であることを特徴とする請求項1に記載の方法。それから私は最大の合計を選んだ。これらの制約で、私はそれがかなり速くなるかもしれないと思うが、より速いアルゴリズムはありますか？私はアルゴリズムの複雑さを数えていませんが、O（a * b * c * c）と思われます。そして、私が最悪の場合に間違っていなければ、それは止まらないかもしれません。

Answer 1

私はこれにアプローチする正しい方法は、整数変換を最初に行うことです：元の行列Mの各要素（i、j）に対して、整数変換行列I(i,j) = sum[0..i, 0..j](M)を計算します。行と列の両方の方向で合計を実行することで、これをO（a * b）時間で実行できます。

あなたは積分変換を持っていたら、あなたのように、一定時間内にの合計に任意のサブブロックを計算することができますので、あなたがのために、一定の時間内に各CXC正方形の合計を計算し、比較することができ

sum[i0..i1, j0..j1](M) = I(i1,j1) - I(i0 - 1, j1) - I(i1, j0 - 1) + I(i0 - 1, j0 - 1) 

合計でO（a * b）である。

Answer 2

あなたの解決策はうまくいくでしょうし、あなたは時間の複雑さについて正しいです、確かにa * b * c * cです。 少し速くする方法の1つは、c * cウィンドウをスライドさせると、すべてを再計算せずに、ウィンドウから移動しているものを減算して、移動中のものを追加するだけですウィンドウに。これをx方向とy方向の両方向で行うことができるので、将来のルックアップのために列（または行）内のすべてのc * cの正方形の合計を覚えておくとよいでしょう。

Answer 3

ここで述べたスライドアプローチでは、複雑さが軽減されると思います。 あなたのケースでは、a、b、cは各最適化問題（cは最適化変数ではない）で一定であると仮定します。

1）左上隅から開始し、O（C *とc）は

2）

3）リピート右端の列の左端の列を除去し、添加した後、右O（C）にスライド（2）（AC）回、O（C×（AC））ので

4）（1） - （3）O約コスト（C *とのC + C *（AC））

5 ）あなたはまた、下にスライドして、他の（bc）行に対してこれを行う必要があります。それぞれO（c）が下にスライドし、O（c * a） + c *（a- C）（BC）+ C（AC）+ C×（BC））

6）、B >> Cを仮定し、それはO（のb * C * A）

できるように簡略化することができます間違ったことがあれば教えてください！