題目1497:面積最大の全1サブマトリックス

タイトルの説明:
1つのM*Nの行列の中で、すべての要素は0と1だけで、この行列の中から1つの面積の最大の全1サブ行列を探し出して、いわゆる最大は要素1の個数が最も多いことを指します.
入力:
入力には、複数のテストサンプルが含まれる場合があります.各テストケースについて、入力される最初の行は2つの整数m、n(1<=m、n<=1000):入力するマトリクスのサイズを表します.行列にはm行があり、各行にはn個の整数があり、それぞれ0または1であり、隣接する2つの数の間に厳密に1つのスペースで区切られている.
出力:
各テストケースに対応して、出力マトリクスの中で面積が最も大きい全1サブマトリクスの要素数.
サンプル入力:

2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

サンプル出力:

0
4

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int mat[1010][1010];
int h[1010];
int l[1010];
int r[1010];
int main() 
{
	int n,m;
	while (scanf ("%d%d",&m,&n) == 2) {
		for (int i = 1;i <= m;i ++) {
			for (int j = 1;j <= n;j ++) {
				scanf ("%d",&mat[i][j]);
			}
		}
		int ans = 0;
		memset(h,0,sizeof(h));
		for(int i = 1;i <= m; i++){
			for(int j = 1; j <= n; j++){
				if(mat[i][j] == 1)
					h[j]++;
				else
					h[j] = 0;
			}
			h[0] = h[n + 1] = -1;
			for(int j = 1;j <= n; j++){
				int k = j;
				while(h[j] <= h[k - 1])
					k = l[k - 1];
				l[j] = k;
			}
			for(int j = n;j >= 1;j--){
				int k = j;
				while(h[j] <= h[k + 1])
					k = r[k + 1];
				r[j] = k;
			}
			for(int j = 1; j <= n; j++){
				if(ans < h[j] * (r[j] - l[j] + 1))
					ans = h[j] * (r[j] - l[j] + 1);
			}
		}	
		cout << ans << endl;	
	}
	return 0;
}