悬线法

参考资料

• 悬线法 - OI Wiki

简介

悬线法 用于求最大子矩形一类问题。把每个点向上引一条尽量长的「悬线」，逐行递推每条悬线能向左、向右扩展到的最远边界及其高度，即可在 $O(nm)$ 内枚举出所有极大子矩形。

例题

洛谷 P4147 玉蟾宫

给定 $n\times m$ 的网格，每格为可用或障碍，求全部由可用格组成的最大子矩形的面积。