エントリがすべて 0 または 1 の配列 M[1..m,1.. n] で表される mXn ビットマップが与えられたとします。すべて 1 のブロックは、M[i .. i0, j .. j0] で、すべてのビットが 1 に等しい. M 内のすべてが 1 で面積が最大のブロックを見つける効率の良いアルゴリズムを説明、解析してください。
動的プログラミング ソリューションを作成しようとしています。しかし、私の再帰アルゴリズムは O(n^n) 時間で実行され、メモ化の後でも O(n^4) 未満に下げることは考えられません。誰かがより効率的な解決策を見つけるのを手伝ってくれますか?
これは単なるアイデアであり、機能するかどうかはわかりません。
A(i,j)(di,dj) を (i,j) から (i+di,j+dj) までのすべてが 1 のブロックとなるように定義します。つまり、i<=x に対して M[x,y]=1 を意味します。 <=i+di および j<=y<=j+dj。
A( i,j)(di+1,dj) と A(i,j)(di,dj+1) が存在しない場合、A(i,j)(di,dj) をmax-blockとして定義します。
各 (i,j) に対して、最大ブロックのリストを作成し、それを L(i,j) と呼びます。リストの最大長は min(m-i+1, n-j+1) <= min(m,n) です。
L(i,j) は、M[i,j]、L(i+1,j)、および L(i,j+1) のみに依存します。L(i+1,j) と L(i,j+1) から L(i,j) を構築することは線形時間で実行できると思います。ソートされたリストのマージについて思い出します。L(i,j) を使用して、L(i,j) の A(i,j)(di,dj) の max(di * dj) を見つけます。これらの値の最大値は、最大オールワン ブロックを指定します。
このアプローチには複雑さ n*m*min(m,n) ~= n^3 があり、必要な最後の 2 行を格納するために min(m,n)^2 スペースが必要です。