作用：可以解决图中满足条件的最大子矩阵的问题。
做法：理性上讲就是枚举每一个点可到达的满足条件的最左端和最右端和最上端，最后得出最大值。
感性的想就是一根线，拉直了分别往左右上探探，以此探到最大值。
（此处讲解一下为什么不往下搜，虽然这个问题有点智障,但我这种负责任(啰嗦)的人还是想讲一讲，其实原因很简单，你要求最值，那你总会枚 举到最值矩阵的下端，所以没必要每个点都搜下端，不然就是浪费了)
定义：l[i][j]:（i,j） 能够满足条件的左边的最值的纵坐标
r[i][j]:（i,j） 能够满足条件的右边的最值的纵坐标
up[i][j]:（i,j） 能够满足条件的上边的最值的横坐标
mp[i][j]:存图的邻接矩阵
知识点：dp
说了这么多开始正题吧，这个算法的模板题（我用的是洛谷4147玉蟾宫，其实还有一个模板题洛谷1169，学完悬线法大家可以去试试）简介：
有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
这片土地被分成N*M个格子，每个格子里写着‘R‘或者‘F‘，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。
现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着‘F‘并且面积最大。
但是rainbow和freda的OI水平都弱爆了，找不出这块土地，而蓝兔也想看freda卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为S，它们每人给你S两银子。
第一行两个整数N,M，表示矩形土地有N行M列。
接下来N行，每行M个用空格隔开的字符‘F‘或‘R‘，描述了矩形土地。
输出一个整数，表示你能得到多少银子，即(3*最大‘F‘矩形土地面积)的值。
输入：
5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F
输出：
45
对于50%的数据，1<=N,M<=200
对于100%的数据，1<=N,M<=1000
其实不难发现这题就是一个求最大矩阵问题（矩阵越大，钱越多啦），而这个数据规模也不算很大，就可以用我们的悬线法啦。
做法上面已经讲了，下面贴出代码（代码里会再次解释）
code:
1 #include<bits/stdc++.h> 2 #define fo(i,j,k) for(register int i=j;i<=k;i++) 3 #define fd(i,j,k) for(register int i=j;i>=k;i--) 4 #define ll long long 5 #define re register 6 #define file(x) freopen("x.in.txt","r",stdin);freopen("x.out.txt","w",stdout); 7 #define ios ios::sync_with_stdio(false) 8 using namespace std; 9 inline int Readc(){ 10 char c=getchar(); 11 while(c!=‘R‘&&c!=‘F‘)c=getchar(); 12 if(c==‘F‘)return 1; 13 return 0; 14 }//快读（应该比较好理解吧） 15 int n,m,ans1,ans,mp[1001][1001]; 16 int l[2018][2018],r[2018][2018]; 17 int up[2018][2018]; 18 int main() 19 { 20 ans=0; 21 cin>>n>>m; 22 fo(i,1,n) 23 fo(j,1,m) 24 { 25 mp[i][j]=Readc(); 26 l[i][j]=j; 27 r[i][j]=j; 28 up[i][j]=1; 29 }//输入和l,r,up数组的初始化 30 fo(i,1,n) 31 fo(j,2,m) 32 { 33 if(mp[i][j]==1 && mp[i][j-1]==1)//需要满足的条件 34 l[i][j]=l[i][j-1];//如果满足了它的最左就等于它左端的最左 35 } 36 fo(i,1,n) 37 fd(j,m-1,1)//此处强调必须从右到左，因为是运用了dp的思想所以要从小到大递推 38 { 39 if(mp[i][j]==1 && mp[i][j+1]==1)//需要满足的条件 40 r[i][j]=r[i][j+1];//如果满足了它的最右就等于它右端的最右 41 } 42 fo(i,1,n) 43 fo(j,1,m)//枚举每个点，统计答案最大值 44 { 45 if(i>1 && mp[i][j]==1 && mp[i-1][j]==1) 46 { 47 r[i][j]=min(r[i][j],r[i-1][j]);//矩阵是个规则图形所以也要考虑上面的部份，总不能是歪歪扭扭的，所以此处还需再次更新一边最值 48 l[i][j]=max(l[i][j],l[i-1][j]);//与上面同理 49 up[i][j]=up[i-1][j]+1;//此处也在统计上面的最值 50 } 51 ans=max(ans,(r[i][j]-l[i][j]+1)*up[i][j]);//答案统计，中间公式应该很好理解就不说了 52 53 }//最后运算答案 54 cout<<ans*3;//输出 55 //完美谢幕 56 return 0; 57 }
到这里ACM悬线法也差不多讲完了，不懂的读者可以用纸画一下，其实真的没那么难，有兴趣的可以去做一下洛谷1169，也是可以用悬线法
这类问题除了悬线法还有二维ST表，线性算法，有兴趣的也可以了解一下。
原文：https://www.cnblogs.com/tomo-ROK/p/12246368.html