@[toc]

普通矩阵（单个矩阵值为任何数）

例题：POJ 1074
在这里插入图片描述
求出其中最大的子矩阵
答案是：
9 2
-4 1
-1 8
最大和是15
我们先想想如果不是矩阵，是一个数组，求其中连续的最长一段，咋做？

最大子段和

我们用b[i]来表示a[0].....a[1]的最大子段和
那么b [ i ] =max ( b [i - 1 ] + a [ i ], a [ i ] )
当a[n] 大于dp[n-1]（前n-1个元素序列的最大子段和）。此时舍弃前面的子段和，即断开。
否则的话，把a[n]连接到前n-1个元素序列的最大和子段上，即dp[n] = dp[n-1] + a[n]

int MaxSum(int n,int *a)
{
    int sum=0,b=0;
    for(int i=0;i<n;i++)
    {
        if(b>0) sum=max(sum,b+a[i]);
        else sum=max(a[i],sum);
    }
    return sum;
}

扩展到二维情况

二维矩阵排列方式如图
参考题解
在这里插入图片描述
如果红色是我们要找的最大子矩阵
那和就是：（a[q][i]+.....+a[p][i],a[q][i+1]+.....+a[p][i+1],........,a[q][j]+........a[p][j]）=（sum1，sum2，.......,sumn）
sum也就是每一列的相同行数相加
这不也是sun的一维数组，那其实就是一个一维数组的最大子段问题
如果把二维数组看成是纵向的一维数组和横向的一维数组

#include <iostream>
#include <cstring>
using namespace std;

int maxsub(int a[], int n)
{
    int i, max = a[0], b = 0;
    for (i = 0; i < n; i++)
    {
        if (b + a[i] >= a[i])    //当n-1的最大字段和+a[i]>=原来的最大字段和
            b += a[i];    //则n的最大字段和为b+a[i]
        else    //否则，就是a[i]
            b = a[i];
        if (b > max)    //找到最大的最大字段和
            max = b;
    }
    return max;
}

int main()
{
    int n, i, j, k, maxsubrec, maxsubarr, m;
    int dp[101][101], arr[101];
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            cin >> dp[i][j];
    maxsubrec = dp[0][0];
    for (i = 0; i < n; i++)    //i用于标识从哪行开始，依次选择行
    {
        memset(arr, 0, sizeof(arr));
        for (j = i; j < n; j++)    //从第i行开始，j为选择几行
        {
            for (k = 0; k < m; k++)    //从1列选择到m列，压缩行
                arr[k] += dp[j][k];//arr表示每列的值
            maxsubarr = maxsub(arr, m);    //从每一个压缩行中选择最大字段和
            if (maxsubarr > maxsubrec) maxsubrec = maxsubarr;
        }
    }
    cout << maxsubrec << endl;
    return 0;
}

01矩阵（单个矩阵值为0或1）

参考题解
POJ - 3494
在这里插入图片描述
其实就是没有负数情况
我一开始想的是将最大子矩阵的代码中，如果一个数为0就赋值为-10000（这样程序就肯定不会选择这个块）
但是这样会超时
针对01矩阵我们可以这么想:
每一个单元格的值等于它所在列的连续1的数量，如果当前行为1，则当前行的值就等于上一行加1，如果当前行为0，则他的值也是0
我们扫描每一行，求出这一行中可形成的矩形最大面积，然后去最大情况即可
然后我们要用到一个单调递减的单调栈，
如果栈为空或者当前元素大于等于栈顶元素，则入栈
若栈非空且当前元素小于栈顶元素，则将栈顶弹出，更新面积最大值，直到栈空或者遇到第一个大于等于当前元素
将最后一个出栈的栈顶元素（最后一个大于当前元素的）向左右延伸，修改其值，并入栈。
核心都是对于每个高度为h的矩形，找到最左高度大于等于它的位置，和最右的位置。
在这里插入图片描述
我们看第三行：
0 1 3 2 0 0 0
0先入栈，然后1入栈，然后3入栈，然后到2时，2<3,计算此时的矩阵面积=（4-3） * 3=3，此时最大面积是3，然后将值3改为2，此时就是0 1 2 2 ，然后0<2,计算此时面积 = (5-3) * 2=4,最大面积就是4,一次类推，都是按照这个操作

代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stack>
using namespace std;

int main()
{
    //top指向栈顶；tmp为临时变量，记录面积的值；ans为答案，记录面积的最大值 
    int i,j,m,n,x,top,tmp,ans,h[2020],a[2020];
    stack<int> st; //单调栈，记录位置 
    while(~scanf("%d%d",&m,&n))
    {
        ans=0;
        memset(h,0,sizeof(h)); //用于第一行的处理
        for(i=0;i<m;i++)
        { //扫描每一行 
            for(j=1;j<=n;j++)
            {
                scanf("%d",&x);
                if(x==1) h[j]=h[j]+1; //如果是1，则在上一行本列的基础上+1 
                else h[j]=0; //否则为0 
                a[j]=h[j]; //a数组用来向左右扩展
            }
            a[n+1]=-1; //设最后元素为最小值，以最后让栈内元素出栈 
            for(j=1;j<=n+1;j++)
            {
                if(st.empty()||a[j]>=a[st.top()])
                { //如果栈为空或入栈元素大于等于栈顶元素，则入栈 
                    st.push(j);
                }
                else
                {
                    while(!st.empty()&&a[j]<a[st.top()])
                    { //如果栈非空并且入栈元素小于栈顶元素，则将栈顶元素出栈 
                        top=st.top();
                        st.pop();
                        tmp=(j-top)*a[top]; //计算面积值 
                        if(tmp>ans) ans=tmp; //更新面积最大值 
                    }
                    st.push(top); //将最后一次出栈的栈顶元素延伸并入栈 
                    a[top]=a[j]; //修改其对应的值 
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}