以下は、0 と 1 で埋められた an*m 行列です。1 で構成される最大の長方形を見つける必要があります。0 で構成される最大の長方形は、1 の代わりに 0 を使用できるため、同等です。したがって、この例では、8x8 マトリックス: .
10011110
10011110
11100010
11100010
11100000
11001111
11000000
11000000
これは宿題ではありません。これは、面接の準備の質問の 1 つです。
次の解決策を思いつきました。(0,0) から開始し、各要素について、可能であれば斜めに移動して、その特定の長方形を形成する他の要素を両方向でチェックします (対角線の端が 2,2 であるとします。2,1 と 1,2 をチェックします)。それ以外の場合は、存在する 1 に応じて左または右に移動します。四角形が展開されている場合は、四角形に含まれる 1 の現在の数でセルをマークします。
どのようにアプローチしますか？私の解決策についてどう思いますか？