前言（吐槽）

第一次知道这个东西，把暴力搜索的扫描法O(nm²)降成了O(nm)

有点腻害。

这玩意是国家队写的论文！作者是咱胡建银！（知网没找到，只能找到百度文库的）

浅谈用极大化思想解决最大子矩形问题-王知昆

开始学习！

传统的扫描法我就不讲了，其实就是暴力求解，直接讲悬线法算法了

算法核心

首先是对几个东西的定义：

定义

最大子矩形问题

在一个给定的矩形中有一些障碍点，找出内部不包含障碍点的，边与整个矩形平行或重合的最大子矩形。

有效子矩型：满足要求的子矩形
极大子矩型：无法再向外拓展的有效子矩形
最大子矩型：最大的一个有效子矩形

显然有，在一个有障碍点的矩形中，最大子矩形一定是极大子矩形

悬线（其实这个挺直白的

有效竖线：除了两个端点以外，不覆盖任何一个障碍点的竖直线段
悬线：上端覆盖了一个障碍点或者到达整个矩形上边界的有效线段

每个悬线上的点的与底部的点一一对应，矩形中每一个点（矩形顶部点除外）都对应了一条悬线。

如果把一条悬线向左右两个方向尽可能的移动，那么就得到了一个矩形。

注意：悬线对应的矩型不一定是极大子矩阵，因为悬线定义中固定了悬线的下边界，故而，悬线左右移动所得到的矩形无法向下扩展。

算法变量

$height _{i, j}$ ：表示以$(i,j)$为底的悬线的高
$left _{i, j}$：表示以$(i,j)$为底的悬线向左最多能移动到的位置
$right _{i, j}$：表示以$(i,j)$为底的悬线向右最多能移动到的位置

初始化（预处理）

$$
\begin{cases}
height_{i, j} & =1 \\
left_{i, j} & =j \\
right_{i, j} & =j
\end{cases}
$$

我们需要对这三个数组进行一次预处理

悬线长度预处理

显然$(i,j)$如果不是障碍点的话，$height _{i, j} = height _{i-1, j} +1$
否则$height _{i, j} = 1$

所以有

$$
height _{i, j}=
\begin{cases}
1 &\text{if }&height _{i-1, j}==0 \\
height _{i-1, j}+1 &\text{if }&height _{i-1, j}==1
\end{cases}
$$

向左移动距离预处理（左右移动都是DP过程）

我们逐层遍历，显然在没有障碍点的情况下，$left_{i,j} = left_{i,j-1}$；而左边点是障碍点时显然$left_{i,j}=j$。所以有

$left_{i,j} = (i,j)\text{左边第一个障碍点/边界位置}+1 = (i,j-1)\text{左边第一个障碍点/边界位置}+1$

如果$(i,j)$的上一个点不是障碍点的情况时有

$left_{i,j} = left_{i-1,j}$

我们整合一下就是

$$
left_{i,j} = \text{max}
\begin{cases}
left_{i-1,j} \\
(i,j-1)\text{左边第一个障碍点/边界位置}+1
\end{cases}
$$

向右移动距离预处理

这个和向左也是类似的，方程如下：

$$
right_{i,j} = \text{min}
\begin{cases}
right_{i-1,j} \\
(i,j+1)\text{右边第一个障碍点/边界位置}-1
\end{cases}
$$

实际操作

因为向左预处理是$j: 0→m-1$,而向右预处理是$j: m-1→0$

原理上来讲这两个不会放到同一个for二层循环里。但取$left/right_{i-1,j}$是自顶向下，无所谓循环从左向右还是从右向左，所以取max和min我们一般放在求最大面积的循环中

故预处理一般只处理$left_{i,j} = left_{i,j-1}$和$right_{i,j} = right_{i,j+1}$，以及高度的预处理，而DP的操作我们丢到求面积的过程中

面积处理

显然对于每段悬线来讲，$S_{i,j} = height_{i,j} * (right_{i,j} - left_{i,j} + 1)$

而$left/right_{i,j}$的DP过程可以放在求面积之前

所以最终处理所需时间是O(nm)

板子

//预处理
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        right[i][j]=left[i][j]=j,up[i][j]=1;
for(int i=1;i<=n;i++)
    for(int j=2;j<=m;j++)
        if(满足条件)
            right[i][j]=right[i][j-1];
for(int i=1;i<=n;i++)
    for(int j=m-1;j>=1;j--)
        if(满足条件)
            left[i][j]=left[i][j+1];

//DP和面积处理
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        if(满足条件){
            right[i][j]=min(right[i][j],right[i-1][j]);
            left[i][j]=max(left[i][j],left[i-1][j]);
            up[i][j]=up[i-1][j]+1;
        }
        s = max(s, up[i][j] * (right[i][j] - left[i][j] + 1));
    }

题目

咕咕咕咕咕

ACM暑假训练：【求极大化矩阵】DP之悬线法