1.求01矩阵中最大子正方形的面积.(n<=1e3)

https://leetcode-cn.com/problems/maximal-square/

分析：考虑动态规划。图片说明 表示以图片说明 为当前最大正方形的右下角时的正方形的最大边长。
那么转移方程：
图片说明 

#include<bits/stdc++.h>
using namespace std;

const int maxn=3e3+10;

int dp[maxn][maxn],a[maxn][maxn];

int main()
{
    int n,m,ans=0;
    cin>>n>>m;
    for( int i=1;i<=n;i++ )
    {
        for( int j=1;j<=m;j++ ) cin>>a[i][j];
    }
    for( int i=1;i<=n;i++ )
    {
        for( int j=1;j<=m;j++ ) 
        {
            if( a[i][j]==1 )
            {
                dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                ans=max(ans,dp[i][j]);
            }
        }
    }
    cout<<ans*ans<<endl;
}

2.求01矩阵中最大的全1子矩阵.

https://leetcode-cn.com/problems/maximal-rectangle/

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

const int maxn=2e3+10;

int dp[maxn][maxn],a[maxn][maxn],h[maxn][maxn],c[maxn],width[maxn];

int main()
{
    int n,m,ans=0;
    while( ~scanf("%d%d",&n,&m) )
    {
        ans=0;
        for( int i=1;i<=n;i++ )
        {
            for( int j=1;j<=m;j++ ) 
            {
                scanf("%d",&a[i][j]);
                h[i][j] = a[i][j] ? h[i - 1][j] + 1 : 0;
            }
            h[i][m + 1] = 0;
        }

        for( int i=1;i<=n;i++ )
        {
            int top=0;
            for( int j=1;j<=m+1;j++ ) 
            {
                if( c[top]<h[i][j] )
                {
                    c[++top]=h[i][j];
                    width[top]=1;
                }
                else
                {
                    int w=0;
                    while( c[top]>h[i][j] )
                    {
                        w+=width[top];
                        ans=max(ans,c[top]*w);
                        top--;
                    }
                    c[++top]=h[i][j];
                    width[top]=w+1;
                }
            }
        }
        printf("%d\n",ans);
    }

}

3.求01矩阵中第二大的全1子矩阵.
题解转：https://blog.nowcoder.net/n/ccb46153ba36421a9eee90a59be12764

4.求子矩阵个数.

  • 全1子正方形个数：
  • 全1子矩阵个数：