首页 > 代码库 > 最大全1子矩阵
最大全1子矩阵
http://blog.csdn.net/zhang20072844/article/details/12925581
给出1个M*N的矩阵M1，里面的元素只有0或1，找出M1的一个子矩阵M2，M2中的元素只有1，并且M2的面积是最大的。输出M2的面积。
Input
第1行:2个数m,n中间用空格分隔(2 <= m,n <= 100)第2 - N + 1行：每行m个数，中间用空格分隔，均为0或1。Output
输出最大全是1的子矩阵的面积。Input 示例
3 31 1 01 1 10 1 1
Output 示例
4
题目分析：
这个题目N=100时可以根据最小子矩阵和求O(N^3)，但是当N范围为1000时，就要求降一个数量级了。
这里我们可以一行一行的求。
比如第一行 1 1 0 1 1 1 0 1
那么我们求和b[]={1,1,0,1,1,1,0,1}
比如第二行为1 1 0 0 0 0 1 1
那么我们继续求和b[]={2,2,0,0,0,0,0,2}......
也就是说：
if(map[i][k])
b[k] ++;
else
b[k] = 0;
这样得到了了一个直方图，不知道大家有没有求过最大直方图面积的问题
就是不同高度的直方图，求这个直方图最大的矩形面积，如何去求？
比如直方图高度为 1 2 3 2，那么最大面积是？
当以第一个为基准的时候高度为1，后面的大于都可以组成矩形，所以面积为4.当以第二个为基准，那么只有后三个可以，面积为6.同理。。。。最大面积为6.
这里也是一样，当求得了第一行到当前行的高度后，可以求出目前的最大面积。
我们设立两个数组l[],r[]分别表示以b[j]为基准时候的左右边界，那么一b[j]为基准的面积就变成了b[j]*(r[j]-l[j]+1)，然后枚举出最大的即可。
对于l[],r[]，我们可以通过下面计算方法获得：
#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)//i表示以第I行作为底端 { for (int k = 1; k <= N; ++ k) { if(map[i][k]) b[k] ++; else b[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];//这么写的话更加快一点，直接写l[j]=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;}
最大全1子矩阵
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。