# UVa 10074

## Summary

A Dynamic Programming problem. (Same with 108 and 10667)

## Explanation

Create matrix A[m][n],where A[i][k]- longest line containing no 1 starting from (i,k). For all (i,k) do l-width j-height

```	for (kk=i,l=1,j=matrix[i][k];kk<m;kk++,l++)
if (matrix[kk][k])
{
if (j>matrix[kk][k]) j=matrix[kk][k];
if (j*l>max) max=j*l;
}else break;
```

## Implementations

```//Created by Zaspire
#include <stdio.h>

int m,n,matrix[100][100];

int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int i,k,j,kk,l,max;
while (scanf("%d %d",&m,&n),m!=0||n!=0)
{
max=0;
for (i=0;i<m;i++)
for (k=0;k<n;k++)
{
scanf("%d",&j);
matrix[i][k]=j;
}
for (j=0;j<m;j++)
{
k=0;
for (i=n-1;i>=0;i--)
{
if (matrix[j][i]==0) k++;
else k=0;
matrix[j][i]=k;
}
}
for (i=0;i<m;i++)
for (k=0;k<n;k++)
if (matrix[i][k])
{
j=matrix[i][k];
if (j>max) max=j;
for (kk=i+1,l=2;kk<m;kk++,l++)
if (matrix[kk][k])
{
if (j>matrix[kk][k]) j=matrix[kk][k];
if (j*l>max) max=j*l;
}else break;
}
printf("%d\n",max);
}
return 0;
}
```

```6 7
0 1 1 0 1 1 0
0 0 0 0 0 1 0
1 1 0 0 0 0 1
0 1 0 1 0 0 1
1 1 0 0 0 1 0
1 1 0 1 1 0 0
6 7
0 1 1 0 1 1 0
0 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 0 1 0 0 1
1 1 0 0 0 1 0
1 1 0 1 1 0 0
0 0
```

```6
8
```