题目描述：
Given a m-by-n (0,1)-matrix, of all its submatrices of all 1’s which is the largest? By largest we mean that the submatrix has the most elements.
在一个n*m的矩阵找到一块全是1的矩阵且保证面积最大；
输入：n,m然后(0,1)矩阵；n,m范围都是2000；
输出：最大面积；
样例：
input:
2 2 0 0 0 0 4 4 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 output: 0 4 这个题和我之前写的一个连续矩形求最大面积的题很像，博客连接; 点击打开链接不同的是那个题所有矩形并排排好，而这个需要你自己去找到矩形，那么我们先将整个矩阵预处理一遍，将每个点向上连续的1的个数作为这个矩形的高度，宽度设为1，处理之后的每一行其实就和之前那个题的情形一样，那么把每一行用单调栈跑一边找到最大值即可。
AC代码：
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<stack> #include<queue> #include<algorithm> using namespace std; struct node { int height; int width; }; int n,m; int a[2010][2010]; struct node b[2010][2010]; int solve(int x) { int ans=0; stack<node > s1; for (int j=1;j<=m;j++) { int tmp=0; while(!s1.empty()&&b[x][j].height<=s1.top().height) { int tot=s1.top().height*(s1.top().width+tmp); if (tot>ans) ans=tot; tmp+=s1.top().width; s1.pop(); } struct node s; s.height=b[x][j].height; s.width=b[x][j].width+tmp; s1.push(s); } int tmp=0; while(!s1.empty()) { int tot=s1.top().height*(s1.top().width+tmp); if (tot>ans) ans=tot; tmp+=s1.top().width; s1.pop(); } return ans; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { memset(a,0,sizeof(a)); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]); memset(b,0,sizeof(b)); for (int j=1;j<=m;j++) { for (int i=1;i<=n;i++) { if (a[i][j]==1) b[i][j].height=b[i-1][j].height+1; else b[i][j].height=0; b[i][j].width=1; } } /*for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) printf("%d ",b[i][j].height); printf("\n"); }*/ int ans=0; for (int i=n;i>=1;i--) ans=max(ans,solve(i)); printf("%d\n",ans); } return 0; }