这个题目跟最大全0子矩阵是类似的。正方形的话，只要把任意极大子正方形（”极大“定义见后面的”论文“）当成把某个极大子矩形去掉一块变成正方形即可，容易解决。
解法1：看论文里面的“算法2“（那个是最大全0子矩阵方法，改一下就可以用在此题）
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int n,m;
int a[][];
int lp[][],rp[][];
int lx[][],rx[][];
int hei[][];
int an1,an2;
int calc(int x,int y)
{
return min(x,y)*min(x,y);
}
int main()
{
int i,j;
scanf("%d%d",&n,&m);
for(i=;i<=n;++i)
{
for(j=;j<=m;++j)
{
scanf("%d",&a[i][j]);
}
}
for(i=;i<=n;++i)
{
lx[i][]=;
for(j=;j<=m;++j)
lx[i][j]=(a[i][j]==a[i][j-])?j:lx[i][j-];
rx[i][m]=m;
for(j=m-;j>=;--j)
rx[i][j]=(a[i][j]==a[i][j+])?j:rx[i][j+];
}
for(i=;i<=n;++i)
{
for(j=;j<=m;++j)
{
if(i!=&&a[i][j]!=a[i-][j])
{
hei[i][j]=hei[i-][j]+;
lp[i][j]=max(lp[i-][j],lx[i][j]);
rp[i][j]=min(rp[i-][j],rx[i][j]);
}
else
{
hei[i][j]=;
lp[i][j]=lx[i][j];
rp[i][j]=rx[i][j];
}
//printf("1t%d %d %d %d %d\n",i,j,hei[i][j],lp[i][j],rp[i][j]);
an1=max(an1,hei[i][j]*(rp[i][j]-lp[i][j]+));
an2=max(an2,calc(hei[i][j],rp[i][j]-lp[i][j]+));
}
}
printf("%d\n",an2);
printf("%d\n",an1);
return ;
}
解法2：
其实最大全0子矩阵还有一种做法：
枚举每一行作为子矩阵的下底部，求出每一列向上最多扩展几行，然后直接用lightoj1083的做法求解此时的最大子矩阵，取所有方案最大值即可
改一下也可以用在此题
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int st[],r[],l[],len;
int an1,an2;
int n,m;
int calc(int x,int y)
{
return min(x,y)*min(x,y);
}
void solve(int *d,int m)
{
int i;
len=;
for(i=;i<=m;++i)
{
while(len>&&d[st[len]]>=d[i]) r[st[len--]]=i-;
l[i]=st[len];
st[++len]=i;
}
while(len>) r[st[len--]]=m;
for(i=;i<=m;++i)
{
an1=max(an1,d[i]*(r[i]-l[i]));
an2=max(an2,calc(d[i],r[i]-l[i]));
}
}
int a[][],hei[][];
int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
for(i=;i<=n;++i)
{
for(j=;j<=m;++j)
{
scanf("%d",&a[i][j]);
hei[i][j]=(i==||a[i][j]==a[i-][j])?:hei[i-][j]+;
}
}
for(i=;i<=n;++i)
{
for(j=;j<=m;j=k+)
{
k=j;
while(k+<=m&&a[i][k+]!=a[i][k]) ++k;
//printf("1t%d %d %d\n",i,j,k);
solve(hei[i]+j-,k-j+);
}
}
printf("%d\n",an2);
printf("%d\n",an1);
return ;
}