ダイナミックプランニング4:最大サブセグメントと問題から最大サブマトリクス問題(4):最大サブマトリクス面積問題

上記は2次元マトリクス(r*c)から、このサブマトリクス内のすべての要素の和が最大になるように、そのサブマトリクスを見つけた.
しかし、この矩形の大きさは必ずしも最大ではないので、最大面積のサブマトリクスを探してみましょう.
転自:『極大化思想で最大子矩形問題を解決する』
質問1:LeetCodeの問題を見てみましょう:LeetCode OJ:Maximal Rectangle
0と1の要素しかない行列に、その中から最大のサブ行列を見つけて、行列内に1しか含まれていないことを満たす.
これは明らかに最大サブマトリクスと問題ではなく,最大サブマトリクス面積の問題である.
アルゴリズムの考え方:
matrix[i][j]=1については、上からiが最も遠くかつ連続する位置Hを見つけ、左からjに最も近い最も遠い1の位置Lは、jから最も遠い1ではなく、右からjに最も近い最も遠い位置Rを見つけ、result=max{result,H*(R-L)}
毎回i,jの要素に対してすべて上の要素を探して、左と右の要素、繰り返し労働が多すぎるならば、配列で保存することができます
matrix[i][j]=1の場合、
H[i][j]は、第i行のサブマトリクスの底辺のサブマトリクスの高さと、この要素から上へ連続する1の個数を表し、H[i][j]=H[i-1][j]+1がある.
L[i][j]は左がjに最も近い最も遠い1の位置を表し、L[i][j]=max{L[i-1][j]があり、j位置の左から最も遠い1の位置}
R[i][j]は、右側がjに最も近い最も遠い1の位置を表し、R[i][j]=min{R[i-1][j]があり、j位置の右側から最も遠い1の位置}
else 
H[i][j]=0;
L[i][j]=0;
R[i][j]=n
iとi-1の関係により、2次元配列を1次元配列処理に変換することができる

class Solution {  
public:  
    int maximalRectangle(vector > &matrix) {  
        if(matrix.empty())return 0;  
        int len=matrix[0].size();  
        vector H(len);  
        vector L(len);  
        vector R(len,len);  
        int result=0;  
        for(int i=0;i=0;j--){  
                if(matrix[i][j]=='1'){  
                    R[j]=min(R[j],right);  
                    result=max(result,H[j]*(R[j]-L[j]));  
                }  
                else right=j;  
            }  
        }  
        return result;  
    }  
};