QBRECT - Hình chữ nhật 0 1
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#define MAX 1111
int a[MAX][MAX];
int h[MAX][MAX];
int stack[MAX];
int l[MAX];
int r[MAX];
int max,m,n;
int size;
void init(void)
{
scanf("%d",&m);
scanf("%d",&n);
int i,j;
for (i=1;i<=n;i=i+1) h[0][i]=0;
for (i=1;i<=m;i=i+1)
for (j=1;j<=n;j=j+1)
{
scanf("%d",&a[i][j]);
if (a[i][j]==0) h[i][j]=0;
else h[i][j]=h[i-1][j]+1;
}
max=0;
}
void process(void)
{
int i,j,tmp;
for (i=1;i<=m;i=i+1)
{
size=0;
l[1]=1;
for (j=2;j<=n;j=j+1)
{
if (h[i][j]>h[i][j-1])
{
l[j]=j;
size++;
stack[size]=j-1;
}
else
{
while ((size>0) && (h[i][stack[size]]>=h[i][j])) size--;
if (size==0) l[j]=1;
else l[j]=stack[size]+1;
}
}
size=0;
r[n]=n;
for (j=n-1;j>=1;j=j-1)
{
if (h[i][j]>h[i][j+1])
{
r[j]=j;
size++;
stack[size]=j+1;
}
else
{
while ((size>0) && (h[i][stack[size]]>=h[i][j])) size--;
if (size==0) r[j]=n;
else r[j]=stack[size]-1;
}
}
tmp=0;
for (j=1;j<=n;j=j+1)
if (tmp<h[i][j]*(r[j]-l[j]+1)) tmp=h[i][j]*(r[j]-l[j]+1);
if (max<tmp) max=tmp;
}
printf("%d",max);
}
int main(void)
{
init();
process();
}