私が考えることができる最良のアルゴリズムは、2Dマトリックスをトラバースし、左上の1つのコーナーから、この場合は右下の向きのコーナーまで、次のようにすることです。
見つけた1ごとに、1の最長の水平方向の文字列と垂直方向の文字列を見つけます。効率を上げるために、右側の位置は左側の位置より1つ少なくなっています(垂直方向の最大値を取得する必要があります)。0に達するたびにカウントを再開するだけです。次の行に到達したときにも同じことが当てはまります。
2つの数値の積は、その位置から始まる長方形の可能な最大面積です。別のデータ構造では、position、maxWidth、およびmaxHeightを格納し、最大の領域が上にある領域に基づいて順序付けを行います。効率を上げるためにサブ長方形を配置することは避けてください。これを行うには、maxHeightがそれ自体の値以下の右隣接1を無視します。データ構造の選択はあなたに任されています。
次に、作成したデータ構造を確認し、最大の長方形から始めます。最も近い0を見つけます。長方形を、0が入っている水平線を除外する2つのサブ長方形と、0が入っている垂直線を除外する2つのサブ長方形に分割します。0がエッジにある場合、3つのサブ長方形のみが取得されます。角にある場合は、2。長方形を削除し、新しく作成したサブ長方形を挿入して、最大の面積の順序を維持します。次に、0のない長方形が見つかるまで、データ構造の次の長方形でこのプロセスを繰り返します。それが最大のものです。
これは、考えられるすべての部分行列をチェックするよりも効率的です。