最大全1子矩阵
题目描述：给出1个M*N的矩阵M1，里面的元素只有0或1，找出M1的一个子矩阵M2，M2中的元素只有1，并且M2的面积是最大的。输出M2的面积。第1行:2个数m,n中间用空格分隔(2 <= m,n <= 100)第2 - N + 1行：每行m个数，中间用空格分隔，均为0或1。输出最大全是1的子矩阵的面积。
for (int j = 1; j <= N; ++ j){l[j] = j;while (l[j] - 1 >= 1 && b[j] <= b[l[j] - 1]){l[j] = l[l[j] - 1];}}for (int j = N; j >= 1; -- j){r[j] = j;while (b[j] <= b[r[j] + 1] && r[j] + 1 <= N){r[j] = r[r[j] + 1];}}
最后可以求最大值：
for (int j = 1; j <= N; ++ j){if (b[j] && (b[j]*(r[j] - l[j]+1) > Max)){Max = b[j]*(r[j] - l[j]+1);}}#include <iostream>#include <cstdlib>#include <cstring>using namespace std;const int MAXN = 510;int map[MAXN][MAXN];int b[MAXN],l[MAXN],r[MAXN];int M,N;int main(){while (cin >> M >> N){int Max = 0;memset(map,0,sizeof(map));for (int i = 1; i <= M; ++ i){for (int j = 1; j <= N; ++j){cin >> map[i][j];}}for (int j = 0; j <= N+1; ++ j){b[j] = 0;}for (int i = 1; i <= M; ++ i){for (int k = 1; k <= N; ++ k){if(map[i][k])b[k] ++;elseb[k] = 0;}/*for (int j = 1; j <= N; ++ j){int p = j;while (p>=1 && b[j] <= b[p--]);int q = j;while(q<=N && b[j] <= b[q ++]);if (b[j] && (b[j]*(q-p-1) > Max)){Max = b[j]*(q-p);}}*/for (int j = 1; j <= N; ++ j){l[j] = j;while (l[j] - 1 >= 1 && b[j] <= b[l[j] - 1]){l[j] = l[l[j] - 1];}}for (int j = N; j >= 1; -- j){r[j] = j;while (b[j] <= b[r[j] + 1] && r[j] + 1 <= N){r[j] = r[r[j] + 1];}}for (int j = 1; j <= N; ++ j){if (b[j] && (b[j]*(r[j] - l[j]+1) > Max)){Max = b[j]*(r[j] - l[j]+1);}}}cout << Max << endl;}return 0;}