2D バイナリ配列 ( と の 2D 配列) があり、0行と列があります。完全にsからなる最大の部分配列 (長方形) の面積を見つける効率的なアルゴリズムを与えてください。1mn1
public int findMaxRectangleArea(int[][] A,int m,int n);
誰かがアルゴリズムの部分で私を助けてくれますか?
質問する
963 次
2 に答える
2
私は次のようなアプローチを試みます：
が見つかるまで、行ごとに左から右に繰り返します0。
これはすでにs の02 つの長方形を識別している可能性があります。1
- その上のすべての行
- 左上から左側の位置まで
0
そのうちの 1 つが大きいことを覚えておいてください。
次に、再帰的に 3 つの未知のセクター (そのうちの 2 つは部分的に未知) に降りていきます。これらのセクターには、既に見つけたものよりも大きな四角形が含まれている可能性があります。
既知の行を再度反復しないようにしてください。これは冗長です。
このソリューションは各フィールドを最大で 2 回 (再帰ステップのセクターが重なる場所) 見ることができるので、θ(x*y) で実行する必要があると思います。
于 2013-02-06T10:58:00.583 に答える
0
それはすべて、最小の配列次元の大きさに依存します。ターゲット プラットフォームの最大ワード サイズより小さい場合は、配列をビットマップの 1D 配列にし、一連のスライディング ビットマスク ウィンドウを使用して四角形を見つけることができます。
于 2013-02-06T10:44:48.107 に答える