長方形探索： 最大長方形の面積 Largest Rectangle

n × n のマス目のそれぞれに 1 または 0 が記してあり、その中から 1 だけから成る最大の長方形の面積を求めて下さい。

これは前に考えた正方形探索の応用で、今回は最大の長方形を探します。この問題も正方形探索で用いたアルゴリズムを応用して動的計画法で解くことができますが、正方形探索ほど単純な式では解決できません。左上角から右下角に向かって個々の要素を計算していく過程で、既に計算された左と上の要素を利用していきますが、長方形探索の場合、W[i][j] の値はそこから左上方向に向かってできる正方形の辺の長さではなく、そこから左上方向に向かってできる全ての長方形の情報を記録する必要があります。このアルゴリズムの詳しい解説が、プログラム・プロムナードに掲載されています。このアルゴリズムは、現在の要素を求めるために重複を避けながら左と上の要素をマージしたりと、プログラムがやや複雑になります。

ここでは、先に考えたヒストグラム内の最大長方形の面積を求めるアルゴリズムを応用したアルゴリズムを示します。このアルゴリズムは上記の正方形探索を応用したアルゴリズムよりもプログラムが簡単になるだけでなく、より効率の良いアルゴリズムです。アルゴリズムはいたって簡単で、まず各要素について上に向かって 1 が何個連続しているかを示すテーブル T を作ります。次に、T の各行をヒストグラムの入力と見なしヒストグラムの最大長方形の面積を求めるアルゴリズムを適用します。

001 #include<stdio.h>
002 #include<iostream>
003 #include<stack>
004 #include<algorithm>
005 #define MAX 105
006 #define BLOCK 0
007 
008 using namespace std;
009 
010 struct Rectangle{ int height;  int pos; };
011 
012 int getLargestRectangle( int size, int buffer[]){
013     stack<Rectangle> S;
014     int maxv = 0;
015     buffer[size] = 0;
016     
017     for ( int i = 0; i <= size; i++ ){
018         Rectangle rect;
019         rect.height = buffer[i];
020         rect.pos = i;
021         if ( S.empty() ){
022             S.push( rect );
023         } else {
024             if ( S.top().height < rect.height ){
025                 S.push( rect );
026             } else if ( S.top().height > rect.height ) {
027                 int target = i;
028                 while ( !S.empty() && S.top().height >= rect.height){
029                     Rectangle pre = S.top(); S.pop();
030                     int area = pre.height * (i - pre.pos);
031                     maxv = max( maxv, area);
032                     target = pre.pos;
033                 }
034                 rect.pos = target;
035                 S.push(rect);
036             }
037         }
038     }
039     return maxv;
040 }
041 
042 int size;
043 int buffer[MAX][MAX];
044 int T[MAX][MAX];
045 
046 int getLargestRectangle(){
047     for ( int i = 0; i < size; i++ ){
048         for ( int j = 0; j < size; j++ ){
049             T[i][j] = 0;
050         }
051     }
052     
053     for ( int j = 0; j < size; j++ ){
054         int sequence = 0;
055         for ( int i = 0; i < size; i++ ){
056             if ( buffer[i][j] == BLOCK ){
057                 sequence = T[i][j] = 0;
058             } else {
059                 T[i][j] = ++sequence;
060             }
061         }
062     }
063     
064     int maxv = 0;
065     for ( int i = 0; i < size; i++ ){
066         maxv = max( maxv, getLargestRectangle( size, T[i] ) );
067     }
068     
069     return maxv;
070 }
071 
072 int main(void){
073     while( cin >> size, size ){
074         for ( int i = 0; i < size; i++ ){
075             for ( int j = 0; j < size; j++ ){
076                 cin >> buffer[i][j];
077             }
078         }
079         cout << getLargestRectangle() << " ";
080     }
081     
082     return 0;
083 }

n 行についてO(n)の計算量なので、これはO(n²)のアルゴリズムとなります。