很久以前，我做过一些最大子矩阵的问题，当时用的是悬线法，这是一个有意思的算法，举例：
（码风稍微有些奇怪，毕竟这是很久以前做的了，忍忍吧）
悬线法的重点在于处理出将每一个点可以向两边扩展的最远位置，再从上到下求出每个点可以向上扩展的位置。
算法复杂度为\(O_{nm}\)，常数有点大。
#include using namespace std;int n,m;int a[1001][1001],l[1001][1001],r[1001][1001],h[1001][1001];int main(){ cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>a[i][j]; l[i][j]=r[i][j]=j; h[i][j]=1; } for(int i=1;i<=n;i++) for(int j=2;j<=m;j++) if(a[i][j]!=a[i][j-1]) l[i][j]=l[i][j-1]; for(int i=1;i<=n;i++) for(int j=m-1;j>=1;j--) if(a[i][j]!=a[i][j+1]) r[i][j]=r[i][j+1]; int ans1=0,ans2=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(i!=1&&a[i][j]!=a[i-1][j]) { l[i][j]=max(l[i][j],l[i-1][j]); r[i][j]=min(r[i][j],r[i-1][j]); h[i][j]=h[i-1][j]+1; } int a=r[i][j]-l[i][j]+1; int b=min(a,h[i][j]); ans1=max(ans1,b*b); ans2=max(ans2,a*h[i][j]); } cout< < <
然而今天在做到时，很显然我写了个悬线法，光荣的获得了\(TLE\)……
#include #include #include #include #include #include #include #include #include #include #include
说实话，这很让我蒙，上网一查，很多人用的是单调栈，好像这两种做法的区别不大，都可以做这一题。
后来发现了王知昆\(Dalao\)的。里面谈到这两种算法的复杂度有较大区别。原话如下：
以上说了两种具有一定通用性的处理算法，时间复杂度分别为\(O_{S^2}\)和\(O_{nm}\) 。两种算法分别适用于不同的情况。从时间复杂度上来看，第一种算法对于障碍点稀疏的情况比较有效，第二种算法则与障碍点个数的多少没有直接的关系（当然，障碍点较少时可以通过对障碍点坐标的离散化来减小处理矩形的面积，不过这样比较麻烦，不如第一种算法好），适用于障碍点密集的情况。
好像有点道理，于是我又将这一题改为了如下的样子：
#include #include #include #include #include #include #include #include #include #include #include
具体思路是将每一行的\(1\)压下来，再按最大子段和来做，但还是\(TLE\)……那是真的爽
后来发现一个很有趣的地方，好像内存大了会\(TLE\)?
再仔细看一下网上的做法，总体思路没太大问题，还是像悬线一样求\(l,r\)，但有人用单调栈求，有人用跳。
先咕着……