问题类型
给定一个含有障碍点的矩形，找出内部不含障碍点的、边与整个矩形平行或重合的最大子矩形。
定义
有效子矩形：内部不含障碍点的、边与整个矩形平行或重合的最大子矩形。
极大子矩形：各边都与障碍点或整个矩形的边重合的有效子矩形。
最大子矩形：最大的有效子矩形。
最大子矩形 $\subseteq$ 极大子矩形 $\subseteq$ 有效子矩形
解决方案
采用 极大化思想
枚举所有极大子矩形，找到最大子矩形。
设矩形为 $n\times m$，障碍点数为 $s$。
算法一
时间复杂度 O( $s^2$ )，空间复杂度 O( $s$ )
思路
首先考虑直接暴力枚举四个边界，然后判断是否为有效子矩形。
时间复杂度 O( $s^5$ )，产生大量的无效子矩形，妥妥的 TLE。
让我们对以上算法进行优化：
将所有障碍点按横坐标排序并编号为 $1,2,3,…$
从左往右枚举极大子矩形左边界，以整个矩形上下边为边界。
向右扫描，枚举障碍点，修改上下边界使矩阵有效，复杂度 O( $s^2$ )。
枚举左右边界时不要忘了加上整个矩形的左右边界！
特点
复杂度比较优秀，适用于障碍点较少的稀疏图
示题
算法二（悬线法）
时间复杂度 O( $n\times m$ )，空间复杂度 O( $n\times m$ )
重点来了！ \拍桌 \拍桌
定义
有效竖线：除了两个端点外，不覆盖任何一个障碍点的竖直线段。
悬线：上端覆盖了一个障碍点或者到达整个矩形上边界的有效竖线。
我们称以点 $(i,j)$ 为底的悬线为点 $(i,j)$ 对应的悬线
思路
一个矩形中共有 $(n-1)\times m$ 条悬线，即除了顶部的点外，其余的各点均有且只有一条与其对应的悬线。
枚举各条悬线，将其向左右两侧尽可能拓展，就可得到一个由 $(n-1)\times m$ 个悬线拓展形成的矩形的集合，而这个集合包含了所有的极大子矩形。
枚举悬线的时间复杂度是 O( $n\times m$ ) 的，即我们要在 O( $1$ ) 内拓展左右区间。
设 height$[ i,j ]$ 为点 $(i,j)$ 对应的悬线的长度，left$[i,j]$ 为点 $(i,j)$ 对应的悬线向左最多拓展到的位置，right$[i,j]$ 为点 $(i,j)$ 对应的悬线向右最多拓展到的位置。
left$[i,j]$ 和 right$[i,j]$先初始化为点 $(i,j)$ 向左右最多拓展到的位置。
这样，若 $(i-1,j)$ 为障碍点，height$[i,j]$=1，left$[i,j]$=0，right$[i,j]$=$m$
若 $(i-1,j)$ 不为障碍点：
height$[i,j]$=height$[i-1,j]+1$
left$[i,j]$=$max$ ( left$[i-1,j]$ , left$[i,j]$ )
right$[i,j]$=$min$ ( right$[i-1,j]$ , right$[i,j]$ )
这样就可以利用递推式，在 O( $1$ ) 的复杂度内拓展左右区间。
特点
复杂度与障碍点数无关，适合障碍点较稠密的矩阵求解，在障碍点较少时，不如算法一。
示题
题解将发至下一篇博客
参考资料
最大子矩阵问题&悬线法 学习笔记 Clove_unique