先說說什么是懸線？就是一條豎線，這條豎線有初始位置和高度兩個性質(zhì)，可以在其上端點不超過當前位置的矩形高度的情況下左右移動。

一、概述

懸線法的適用范圍是單調(diào)棧的子集。具體來說，懸線法可以應用于滿足以下條件的題目：

（1）需要在掃描序列時維護單調(diào)的信息；

（2）可以使用單調(diào)棧解決；

（3）不需要在單調(diào)棧上二分。

看起來懸線法可以被替代，用處不大，但是懸線法概念比單調(diào)棧簡單，更適合初學 OI 的選手理解并解決最大子矩陣等問題。

二、實例講解

懸線法是一種比較簡單的DP技巧，主要用于在的時間內(nèi)解決最大矩形/最大正方形問題，即，給出一個的方格矩陣，其中某些方格是不可選的，求可選的最大矩形/正方形。

其實這個問題用單調(diào)棧也是可以解決的，但懸線法是一種思路更簡單的方法。我們定義“懸線”是從某一格出發(fā)，一直向上能延申的最長豎線（如下圖）。

我們定義極大矩形是無法再向上、下、左或右拓展的矩形，很明顯，每一個最大矩形，都一定是一個極大矩形（否則拓展后的矩形比它更大，它就不是最大的了）。

一個重要的事實是：每個極大矩形都一定可以由某條懸線“拓展”（即把懸線盡可能地往左、往右平移）得到。實際上，在矩形上邊界上找到一個不能再向上的方格（作為極大矩形，一定存在這樣的方格），把它跟矩形下邊界的對應格連線，即可得到這樣的懸線。

由于一個可選的格子對應一條懸線，所以懸線最多只有條。因此，我們只需要枚舉最多條懸線就可以枚舉所有的極大矩形，最大矩形一定就在其中。

接下來是十分簡單的DP環(huán)節(jié)。定義分別表示從某格出發(fā)向上、左、右最多能走多少格（包括自身），則：

然后我們定義 L、R 分別表示從當前格向上的懸線最多能向左、向右拓展多少格，則：

實際上我們發(fā)現(xiàn)分別可以用同一個數(shù)組來存，可以節(jié)省很多空間。對于每一格來說，它對應的懸線左右拓展能得到的最大的矩形面積為：

代碼如下：

for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
        if (A[i][j])
            l[i][j] = l[i][j - 1] + 1;for (int i = 1; i <= n; ++i)
    for (int j = m; j >= 1; --j)
        if (A[i][j])
            r[i][j] = r[i][j + 1] + 1;for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
        if (A[i][j]) {
            u[i][j] = u[i - 1][j] + 1;
            if (A[i - 1][j]) cmin(l[i][j], l[i - 1][j]), cmin(r[i][j], r[i - 1][j]);
            cmax(ans, (r[i][j] + l[i][j] - 1) * u[i][j]);
        }

現(xiàn)在我們解決了最大矩形問題，那么最大正方形呢？很簡單，因為最大正方形一定是最大矩形的子正方形。所以我們只需枚舉所有懸線，計算每條懸線所對應矩形的最大子正方形面積：