因为这道题的情况比较少，即最大值只可能在字母a，b，c之间产生，所以可以枚举3中情况，之后取最大值即可。取最大值时用动态规划的思想做，先对列统计，即高度。之后再对行统计，即宽度。再统计宽度的时候用到了并查集的思想，设置两个属性，left和right，如果后面的高度大于前面的高度，说明后面的left属性可以左移。同理，如果前面的高度小于后面的高度，说明前面的right属性可以右移。这样一直移动，直到所取到得矩形最大为止，再乘以高度，即得到该高度下的最大矩形。题目：
Largest Submatrix
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 479 Accepted Submission(s): 259
Problem Description
Now here is a matrix with letter 'a','b','c','w','x','y','z' and you can change 'w' to 'a' or 'b', change 'x' to 'b' or 'c', change 'y' to 'a' or 'c', and change 'z' to 'a', 'b' or 'c'. After you changed it, what's the largest submatrix
with the same letters you can make?
with the same letters you can make?
Input
The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 1000) on line. Then come the elements of a matrix in row-major order on m lines each with n letters. The input ends once EOF is met.
Output
For each test case, output one line containing the number of elements of the largest submatrix of all same letters.
Sample Input
2 4 abcw wxyz
Sample Output
3
ac代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#define M 1010
int r[M],l[M],height[M][M];
char str[M][M];
int n,m,ans;
int max(int a,int b){
return a>b?a:b;
}
void dp(){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
l[j]=j;r[j]=j;
}
for(int j=1;j<=m;++j){
height[i][0]=-1;height[i][m+1]=-1;
}
for(int j=1;j<=m;++j){
while(height[i][j]<=height[i][l[j]-1]){
l[j]=l[l[j]-1];
}
}
for(int j=m;j>=1;--j){
while(height[i][j]<height[i][r[j]+1]){
r[j]=r[r[j]+1];
}
}
for(int j=1;j<=m;++j){
ans=max(ans,(r[j]-l[j]+1)*height[i][j]);
}
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;++i)
scanf("%s",str[i]+1);
ans=0;
memset(height,0,sizeof(height));
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(str[i][j]=='a'||str[i][j]=='w'||str[i][j]=='y'||str[i][j]=='z')
height[i][j]=height[i-1][j]+1;
}
}
dp();
memset(height,0,sizeof(height));
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(str[i][j]=='b'||str[i][j]=='w'||str[i][j]=='x'||str[i][j]=='z')
height[i][j]=height[i-1][j]+1;
}
}
dp();
memset(height,0,sizeof(height));
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(str[i][j]=='c'||str[i][j]=='y'||str[i][j]=='x'||str[i][j]=='z')
height[i][j]=height[i-1][j]+1;
}
}
dp();
printf("%d\n",ans);
}
return 0;
}