described-推广普通话黑板报

王知昆 第 1 页 IOI2003国家集训队论文
浅谈用极大化思想解决最大子矩形问题

福州第三中学 王知昆

【摘要】

本文针对一类近期经常出现的有关最大（或最优）子矩形及相关变
形问题，介绍了极大化思想在这类问题中的应用。分析了两个具有一定
通用性的算法。并通过一 些例题讲述了这些算法选择和使用时的一些技
巧。

【关键字】
矩形，障碍点，极大子矩形

【正文】
一、 问题
最大子矩形问题：在 一个给定的矩形网格中有一些障碍点，要找出网格内部不
包含任何障碍点，且边界与坐标轴平行的最大子 矩形。

这是近期经常出现的问题，例如冬令营2002的《奶牛浴场》，就属于最大
子矩形问题。

Winter Camp2002,奶牛浴场
题意简述：（原题见论文附件） < br>John要在矩形牛场中建造一个大型浴场，但是这个大型浴场不能包含任何
一个奶牛的产奶点， 但产奶点可以出在浴场的边界上。John的牛场和规划的浴
场都是矩形，浴场要完全位于牛场之内，并 且浴场的轮廓要与牛场的轮廓平行
或者重合。要求所求浴场的面积尽可能大。
参数约定：产奶 点的个数S不超过5000,牛场的范围N×M不超过30000
×30000。

二、 定义和说明
首先明确一些概念。

1、定义有效子矩形为内部不包 含任何障碍点且边界与坐标轴平行的子矩形。如
图所示，第一个是有效子矩形（尽管边界上有障碍点）， 第二个不是有效子矩形
（因为内部含有障碍点）。

王知昆 第 2 页 IOI2003国家集训队论文

2、极大有效子矩形：一个有效子矩形，如果不存在包含它 且比它大的有效子矩
形，就称这个有效子矩形为极大有效子矩形。（为了叙述方便，以下称为极大子矩形）

3、定义最大有效子矩形为所有有效子矩形中最大的一个（或多个）。以下简称为
最大子矩形。


三、 极大化思想
【定理1】在一个有障碍点的矩形中的最大子矩形一定是一个极大子
矩形。

证明：如果最大子矩形A不是一个极大子矩形，那么根据极大子矩形的定义，存
在一个包含A且比A更大 的有效子矩形，这与“A是最大子矩形”矛盾，所以【定
理1】成立。

四、 从问题的特征入手，得到两种常用的算法
定理1虽然很显然，但却是很重要的。根据定理1，我们可以 得到这样一
个解题思路：通过枚举所有的极大子矩形，就可以找到最大子矩形。下面根据
这个思 路来设计算法。
约定：为了叙述方便，设整个矩形的大小为n×m，其中障碍点个数为s。


算法1
算法的思路是通过枚举所有的极大子矩形找出最大子矩形。根据这个思路
可以发现，如果算法中有一次枚举的子矩形不是有效子矩形、或者不是极大子
矩形，那么可以肯 定这个算法做了“无用功”，这也就是需要优化的地方。怎
样保证每次枚举的都是极大子矩形呢，我们先 从极大子矩形的特征入手。

【定理2】：一个极大子矩形的四条边一定都不能向外扩展。更 进一步地说，一
个有效子矩形是极大子矩形的充要条件是这个子矩形的每条边要么覆盖了一
个障 碍点，要么与整个矩形的边界重合。

王知昆 第 3 页 IOI2003国家集训队论文
定理2的正确性很显然，如果一个有效子矩形的某一条边既没有覆盖一 个
障碍点，又没有与整个矩形的边界重合，那么肯定存在一个包含它的有效子矩
形。根据定理2 ，我们可以得到一个枚举极大子矩形的算法。为了处理方便，
首先在障碍点的集合中加上整个矩形四角上 的点。每次枚举子矩形的上下左右
边界（枚举覆盖的障碍点），然后判断是否合法（内部是否有包含障碍 点）。这
样的算法时间复杂度为O(S
5
)，显然太高了。考虑到极大子矩形不能包含 障碍
点，因此这样枚举4个边界显然会产生大量的无效子矩形。
考虑只枚举左右边界的情况。对于已经确定的左右边界，
可以将所有处在这个边界内的
点按从上到下排序，如图1中 所
示，每一格就代表一个有效子矩
形。这样做时间复杂度为O(S
3
)。由于确保每次得到的矩形都是
合法的，所以枚举量比前一种算
法小了很多。但需要注意的是 ，
这样做枚举的子矩形虽然是合
法的，然而不一定是极大的。所
以这个算法还有优化的 余地。通过对这个算法不足之处的优化，我们可以得到
一个高效的算法。
回顾上面的算法，我 们不难发现，所枚举的矩形的上下边界都覆盖了障碍
点或者与整个矩形的边界重合，问题就在于左右边界 上。只有那些左右边界也
覆盖了障碍点或者与整个矩形的边界重合的有效子矩形才是我们需要考察的极大子矩形，所以前面的算法做了不少“无用功”。怎么减少“无用功”呢，
这里介绍一种算法（算 法1），它可以用在不少此类题目上。
算法的思路是这样的，先枚举极大子矩形的左边界，然后从左到 右依次扫
描每一个障碍点，并不断修改可行的上下边界，从而枚举出所有以这个定点为
左边界的 极大子矩形。考虑如图2中的
三个点，现在我们要确定所有以1号点
为左边界的极大矩形。先将 1号点右边
的点按横坐标排序。然后按从左到右的
顺序依次扫描1号点右边的点，同时记
录下当前的可行的上下边界。
开始时令当前的上下边界分别为
整个矩形的上下边界。然后开 始扫描。
第一次遇到2号点，以2号点作为右边
界，结合当前的上下边界，就得到一个
极大子矩形（如图3）。同时，由于所
求矩形不能包含2号点，且2号点在1
号点的下方，所以 需要修改当前的下边
界，即以2号点的纵坐标作为新的下边
界。第二次遇到3号点，这时以3号 点
的横坐标作为右边界又可以得到一个
满足性质1的矩形（如图4）。类似的，

王知昆 第 4 页 IOI2003国家集训队论文
需要相应地修改上边界。以此类推，如
果这个点是在当前点（确定左边界的
点）上方，则修改上边界；如果在下方，
则修改下 边界；如果处在同一行，则可
中止搜索（因为后面的矩形面积都是0
了）。由于已经在障碍点集 合中增加了
整个矩形右上角和右下角的两个点，所
以不会遗漏右边界与整个矩形的右边
重合的极大子矩形（如图5）。需要注
意的是，如果扫描到的点不在当前的上
下边界内，那么就 不需要对这个点进行
处理。
这样做是否将所有的极大子矩形
都枚举过了呢？可以发现 ，这样做只考
虑到了左边界覆盖一个点的矩形，因此
我们还需要枚举左边界与整个矩形的
左边界重合的情况。这还可以分为两类
情况。一种是左边界与整个举行的左边
界重合，而右边 界覆盖了一个障碍点的情况，对于这种情况，可以用类似的方
法从右到左扫描每一个点作为右边界的情况 。另一种是左右边界均与整个矩形
的左右边界重合的情况，对于这类情况我们可以在预处理中完成：先将 所有点
按纵坐标排序，然后可以得到以相邻两个点的纵坐标为上下边界，左右边界与
整个矩形的 左右边界重合的矩形，显然这样的矩形也是极大子矩形，因此也需
要被枚举到。
通过前面两步 ，可以枚举出所有的极大子矩形。算法1的时间复杂度是
O(S
2
)。这样，可以解决 大多数最大子矩形和相关问题了。


虽然以上的算法（算法1）看起来是比较高效 的，但也有使用的局限性。
可以发现，这个算法的复杂度只与障碍点的个数s有关。但对于某些问题，s
最大有可能达到n×m，当s较大时，这个算法就未必能满足时间上的要求了。
能否设计出一种 依赖于n和m的算法呢？这样在算法1不能奏效的时候我们还
有别的选择。我们再重新从最基本的问题开 始研究。


算法2
首先，根据定理1：最大有效子矩形一 定是一个极大子矩形。不过与前一
种算法不同的是，我们不再要求每一次枚举的一定是极大子矩形而只要 求所有
的极大子矩形都被枚举到。看起来这种算法可能比前一种差，其实不然，因为
前一种算法 并不是完美的：虽然每次考察的都是极大子矩形，但它还是做了一
定量的“无用功”。可以发现，当障碍 点很密集的时候，前一种算法会做大量
没用的比较工作。要解决这个问题，我们必须跳出前面的思路，重 新考虑一个
新的算法。注意到极大子矩形的个数不会超过矩形内单位方格的个数，因此我

王知昆 第 5 页 IOI2003国家集训队论文
们有可能找出一种时间复杂度是O(N×M)的算法。

定义：
有效竖线：除了两个端点外，不覆盖任何障碍点的
竖直线段。
悬线：上端点覆盖了一 个障碍点或达到整个矩形上
端的有效竖线。如图所示的三个有效竖线都是悬
线。


对于任何一个极大子矩形，它的上边界上要么有一个障碍点，要么和整个
矩形的上边界重合。那么如果把一个极大子矩形按x坐标不同切割成多个（实
际上是无数个）与y轴垂直 的线段，则其中一定存在一条悬线。而且一条悬线
通过尽可能地向左右移动恰好能得到一个子矩形（未必 是极大子矩形，但只可
能向下扩展）。通过以上的分析，我们可以得到一个重要的定理。
< br>【定理3】：如果将一个悬线向左右两个方向尽可能移动所得到的有效子矩形
称为这个悬线所对应 的子矩形，那么所有悬线所对应的有效子矩形的集合一
定包含了所有极大子矩形的集合。

定理3中的“尽可能”移动指的是移动到一个障碍点或者矩形边界的位置。
根据【定理3】可 以发现，通过枚举所有的悬线，就可以枚举出所有的极
大子矩形。由于每个悬线都与它底部的那个点一一 对应，所以悬线的个数＝
(n-1)×m（以矩形中除了顶部的点以外的每个点为底部，都可以得到一个 悬线，
且没有遗漏）。如果能做到对每个悬线的操作时间都为O(1)，那么整个算法的
复杂度 就是O(NM)。这样，我们看到了解决问题的希望。
现在的问题是，怎样在O(1)的 时间内完成对每个悬线的操作。我们知道，
每个极大子矩形都可以通过一个悬线左右平移得到。所以，对 于每个确定了底
部的悬线，我们需要知道有关于它的三个量：顶部、左右最多能移动到的位置。
对于底部为(i,j)的悬线，设它的高为hight[i,j],左右最多能移动到的位置为
left [i,j],right[i,j]。为了充分利用以前得到的信息，我们将这三个函数用
递推的形式给 出。

对于以点(i,j)为底部的悬线：
如果点(i－1,j)为障碍点， 那么，显然以(i,j)为底的悬线高度为1，而且
左右均可以移动到整个矩形的左右边界，即

height[i,j]1



left[i,j]0

right[i,j]m


如果点(i－1,j)不是障碍点，那么，以(i,j)为底的悬线就等于以(i-1,j)
为 底的悬线＋点(i,j)到点(i-1,j)的线段。因此，
height[i,j]=height[ i-1,j]+1。比较麻烦的是左右边界，先考虑left[i,j]。
如下图所示，(i,j)对应 的悬线左右能移动的位置要在(i-1,j)的基础上变化。

王知昆 第 6 页 IOI2003国家集训队论文

left[i1,j]
即left[i,j]= max


(i1,j)左边第一个障碍点的位置



left[i-1,j]
某个障碍
(i-1,j)
(i,j):当前

right[i,j]的求法类似。综合起来，可以得到这三个参数的递推式：



height[i,j]height[i1,j]1


left[i1,j]


left[i,j]max

 (i1,j)左边第一个障碍点位置



right[i1, j]

right[i,j]min



(i-1,j)右边第一个障碍点位置

left[i,j]
（边界0也算障碍点）


（边界m也算障碍点）

这样做充分利用了以前得到的信息，使每个悬线的处理时间复杂度为
O(1)。对于以点 (i,j)为底的悬线对应的子矩形，它的面积为
(right[i,j]-left[i,j])*h eight[i,j]。
这样最后问题的解就是：
Result＝
max

(right[i,j]left[i,j])*height[i,j] (1in,1jm)

整个算法的时间复杂度为O(NM)，空间复杂度是O(NM)。

两个算法的对比：
以上说了两种具有一定通用性的处理算法，时间复杂度分别为O(S
2)和
O(NM)。两种算法分别适用于不同的情况。从时间复杂度上来看，第一种算法
对于 障碍点稀疏的情况比较有效，第二种算法则与障碍点个数的多少没有直接
的关系（当然，障碍点较少时可 以通过对障碍点坐标的离散化来减小处理矩形
的面积，不过这样比较麻烦，不如第一种算法好），适用于 障碍点密集的情况。

五、 例题

王知昆 第 7 页 IOI2003国家集训队论文
将前面提出的两种算法运用于具体的问题。
1、 Winter Camp2002,奶牛浴场
分析：
题目的数学模型就是给出一个矩形和矩 形中的一些障碍点，要求出矩形
内的最大有效子矩形。这正是我们前面所讨论的最大子矩形问题，因此前 两
种算法都适用于这个问题。
下面分析两种算法运用在本题上的优略：
对于第一种 算法，不用加任何的修改就可以直接应用在这道题上，时间
复杂度为O(S
2
)，S为 障碍点个数；空间复杂度为O(S)。
对于第二种算法，需要先做一定的预处理。由于第二种算法复杂 度与牛
场的面积有关，而题目中牛场的面积很大（30000×30000），因此需要对数
据 进行离散化处理。离散化后矩形的大小降为S×S，所以时间复杂度为
O(S
2
)，空 间复杂度为O(S)。说明：需要注意的是，为了保证算法能正确执
行，在离散化的时候需要加上S个点 ，因此实际需要的时间和空间较大，而
且编程较复杂。
从以上的分析来看，无论从时空效率还 是编程复杂度的角度来看，这道
题采用第一种算法都更优秀。


2、 OIBH模拟赛1,提高组，Candy
题意简述：（原题见论文附件）
一个被分为 n*m 个格子的糖果盒，第 i 行第 j 列位置的格子里面有
a [i,j] 颗糖。但糖果盒 的一些格子被老鼠洗劫。现在需要尽快从这个糖果
盒里面切割出一个矩形糖果盒，新的糖果盒不能有洞， 并且希望保留在新糖
果盒内的糖的总数尽量多。
参数约定：
1

≤ n，m ≤ 1000


分析
首先需要注意的是：本题的模型是一个矩阵 ，而不是矩形。在矩阵的情
况下，由于点的个数是有限的，所以又产生了一个新的问题：最大权值子矩< br>阵。

定义：
有效子矩阵为内部不包含任何障碍点的子矩形。 与有效子矩形不同，有效子
矩阵地边界上也不能包含障碍点。
有效子矩阵的权值（只有有效子矩形才有权值）为这个子矩阵包含的所有点
的权值和。
最大权值有效子矩阵为所有有效子矩阵中权值最大的一个。以下简称为最大
权值子矩阵。

本题的数学模型就是正权值条件下的最大权值子矩阵问题。再一次利用
极大化思想， 因为矩阵中的权值都是正的，所以最大权值子矩阵一定是一个
极大子矩阵。所以我们只需要枚举所有的极 大子矩阵，就能从中找到最大权
值子矩阵。同样，两种算法只需稍加修改就可以解决本题。下面分析两种 算

王知昆 第 8 页 IOI2003国家集训队论文
法应用在本题上的优略：
对于第一种算法，由于矩形中障碍点的个数是不确定的，而且最大有 可
能达到N×M,这样时间复杂度有可能达到O(N
2
M
2
)，空间 复杂度为O(NM)。此
外，由于矩形与矩阵的不同，所以在处理上会有一些小麻烦。
对于第 二种算法，稍加变换就可以直接使用，时间复杂度为O(NM),空间
复杂度为O（NM）。

可以看出，第一种算法并不适合这道题，因此最好还是采用第二种算法。


3、 Usaco Training, Section 1.5.4, Big Barn
题意简述（原题见论文附件）
Farmer John想在他的正方形农场上建一个正方形谷仓。由于农场上有
一些树，而且Farmer John 又不想砍这些树，因此要找出最大的一个不包含
任何树的一块正方形场地。每棵树都可以看成一个点。
参数约定：牛场为N×N的，树的棵数为T。N≤1000,T≤10000。
分析：
这题是矩形上的问题，但要求的是最大子正方形。首先，明确一些概念。
1、定义有效子正方形为内部不包含任何障碍点的子正方形
2、定义极大有效子正方形为不能再向外扩展的有效子正方形，一下简称
极大子正方形
3、定义最大有效子正方形为所有有效子正方形中最大的一个（或多个），
以下简称最大子正方形。

本题的模型有一些特殊，要在一个含有一些障碍点的矩形中求最大子正
方形。这与前 两题的模型是否有相似之处呢？还是从最大子正方形的本质开
始分析。
与前面的情况类似，利用极大化思想，我们可以得到一个定理：
【定理4】：在一个有障碍点的矩形中的最大有效子正方形一定是一个极大
有效子正方形。

根据【定理4】,我们只需要枚举出所有的极大子 正方形，就可以从中找
出最大子正方形。极大子正方形有什么特征呢？所谓极大，就是不能再向外
扩展。如果是极大子矩形，那么不能再向外扩展的充要条件是四条边上都覆
盖了障碍点（【定理2】） 。类似的，我们可以知道，一个有效子正方形是极大
子正方形的充要条件是它任何两条相邻的边上都覆盖 了至少一个障碍点。根
据这一点，可以得到一个重要的定理。
【定理5】：每一个极大子正方 形都至少被一个极大子矩形包含。且这个极大
子正方形一定有两条不相邻的边与这个包含它的极大子矩形 的边重合。

根据【定理5】,我们只需要枚举所有的极大子矩形，并检查它所包含的
极大子正方形（一个极大子矩形包含的极大子正方形都是一样大的）是否是
最大的就可以了。这样，问 题的实质和前面所说的最大子矩形问题是一样的，
同样的，所采用的算法也是一样的。

王知昆 第 9 页 IOI2003国家集训队论文
因为算法1和算法2都 枚举出了所有的极大子矩形，因此，算法1和算
法2都可以用在本题上。具体的处理方法如下：对于每一 个枚举出的极大子
矩形，如图所示，如果它的边长为a、b，那么它包含的极大子正方形的边长
即为min(a,b)。
考虑到N和T的大小不同，所以不
同的算法会有不同的效果。下面分 析两
种算法应用在本题上的优略。
对于第一种算法，时间复杂度为
O(T
2
)，对于第二种算法，时间复杂度为
O(N
2
)。因为N角度看，第二种算法要比第一种算法好。
考虑到两个算法的空间复杂度都可以承
受，所以选择第二种算法较好些。
以下是第一种和第二种算法编程实
现后在USACO Training Program
Gateway上的运行时间。可以看出，在数据较大时，算法2的效率比算法1
高。

算法1：
Test 1: 0.009375
Test 2: 0.009375
Test 3: 0.009375
Test 4: 0.009375
Test 5: 0.009375
Test 6: 0.009375
Test 7: 0.021875
Test 8: 0.025
Test 9: 0.084375
Test 10: 0.3875
Test 11: 0.525
Test 12: 0.5625
Test 13: 0.690625
Test 14: 0.71875
Test 15: 0.75


以上，利用 极大化思想和前面设计的两个算法，通过转换模型，解决了
三个具有一定代表性的例题。解题的关键就是 如何利用极大化思想进行模型
转换和如何选择算法。



算法2：
Test 1: 0.009375
Test 2: 0.009375
Test 3: 0.009375
Test 4: 0.009375
Test 5: 0.009375
Test 6: 0.00625
Test 7: 0.009375
Test 8: 0.009375
Test 9: 0.0125
Test 10: 0.021875
Test 11: 0.028125
Test 12: 0.03125
Test 13: 0.03125
Test 14: 0.03125
Test 15: 0.034375
五、小结

王知昆 第 10 页 IOI2003国家集训队论文
设计算法 要从问题的基本特征入手，找出解题的突破口。本文介绍了两种
适用于大部分最大子矩形问题及相关变型 问题的算法，它们设计的突破口就是
利用了极大化思想，找到了枚举极大子矩形这种方法。
在 效率上，两种算法对于不同的情况各有千秋。一个是针对障碍点来设计
的，因此复杂度与障碍点有关；另 一个是针对整个矩形来设计的，因此复杂度
与矩形的面积有关。虽然两个算法看起来有着巨大的差别，但 他们的本质是相
通的，都是利用极大化思想，从枚举所有的极大有效子矩形入手，找出解决问
题 的方法。

需要注意的是，在解决实际问题是仅靠套用一些现有算法 是不够的，还需
要对问题进行全面、透彻的分析,找出解题的突破口。
此外，如果采用极大化 思想，前面提到的两种算法的复杂度已经不能再降
低了，因为极大有效子矩形的个数就是O(NM)或O (S
2
)的。如果采用其他算法，
理论上是有可能进一步提高算法效率，降低复杂度的 。



七、 附录：
1、几个例题的原题。 见论文附件.doc

2、例题的程序。 见论文附件.doc
说明：所有程序均在Free Pascal IDE for Dos, Version 0.9.2上
编译运行


参考书目
1、 信息学奥林匹克 竞赛指导
----1997～1998竞赛试题解析
吴文虎 王建德 著
2、 IOI99中国集训队优秀论文集
3、 信息学奥林匹克（季刊）
4、 《金牌之路 竞赛辅导》
江文哉主编 陕西师范大学出版社出版