面積最大的全1矩陣

題目描述：

在一個M * N的矩陣中，所有的元素只有0和1，從這個矩陣中找出一個面積最大的全1子矩陣，所謂最大是指元素1的個數最多。

輸入：

輸入可能包含多個測試樣例。
對於每個測試案例，輸入的第一行是兩個整數m、n(1<=m、n<=1000)：代表將要輸入的矩陣的大小。
矩陣共有m行，每行有n個整數，分別是0或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

解題思路： 從第一行開始，一行一行向下掃描，記錄每一列當前的1的個數（碰到0時候清零，可以理解為高度，記錄其為h[i ]），然後計算每一列的符合該列高度的矩形有多寬（對第j列而言，寬度為r[j]-l[j]+1）最後遍歷完所有行得到的最大面積就是答案。
AC代碼：

#include
#include

using namespace std;

int matrix[1005][1005];
int h[1005];
int r[1005];
int l[1005];

int main(int argc,char *argv[])
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		int i,j,k;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf("%d",&matrix[i][j]);
			}
		}
		memset(h,0,sizeof(h));
		int ans=0;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				if(matrix[i][j]==1)
					h[j]++;
				else
					h[j]=0;
			}
			h[0]=h[m+1]=-1;
			for(j=1;j<=m;j++)//l[i]表示h[i]左邊最遠的一個h值不小於h[i]的位置
			{             //即l[i]到i的所有h值均>=h[i],r[i]同理
				k=j;
				while(h[j]<=h[k-1])
					k=l[k-1];
				l[j]=k;
			}
			for(j=m;j>=1;j--)//r[i]表示h[i]右邊最遠的一個h值不小於h[i]的位置
			{
				k=j;
				while(h[j]<=h[k+1])
					k=r[k+1];
				r[j]=k;
			}
			for(j=1;j<=m;j++)
			{
				if(ans