Question

Largest Empty Interval

一条阵列，有些格子已被放上障碍物。最长的、连续的空白格子在哪裡？

Recurrence

length(i) =
 { 0                 , if i < 0                    [Exterior]
 { 0                 , if i = 0 and array[i] = 0   [Initial]
 { 1                 , if i = 0 and array[i] = 1   [Initial]
 { 0                 , if i > 0 and array[i] = 0   [Compute]
 { length(i-1) + 1   , if i > 0 and array[i] = 1   [Compute]

length(i)：以第 i 格作为最右端的连续空白的长度。
array[i]：障碍物为 0，空白为 1。

时间複杂度为 O(N)，空间複杂度为 O(N)，N 为阵列长度。

如果只想计算一个特定问题的答案，那麽空间複杂度可以精简成 O(1)。

程式码：求出最长空白的长度

程式码：求出最长空白的长度

为了让程式码更清爽，这裡把 array[]、length[]裡面的数值都往右移动一格，如此就可以省略掉第零格的判断式，也避免了 length[]会溢出边界。

Largest Empty Rectangle

Largest Empty Rectangle

一张方格纸，许多格子填入黑色。请找出不包含黑格子的矩形，令矩形面积尽量大。

矩形的顶点，是一整个格子，而不是直线与横线的交叉点。

UVa 10074 10502 10667

直觉的演算法：穷举法

矩形总共四个顶点，穷举所有可能的顶点位置。纸的长宽为 H 和 W 的话，总共 H*W 个位置可以放上顶点。穷举所有矩形，时间複杂度是 O((H*W)^4)。另外还得确认矩形不含黑格子，就是 O((H*W)^5)。

想要确定一个矩形的大小和位置，其实只要两个对角顶点就够了；穷举所有矩形，时间複杂度是 O((H*W)^2)。确认矩形不含黑格子，就是 O((H*W)^3)。

想要确定一个矩形的大小和位置，也可以利用左上角的顶点、长、宽；穷举所有矩形，时间複杂度是 O((H*W)^2)。确认矩形不含黑格子，就是 O((H*W)^3)。

预先计算二维前缀和，就能迅速计算二维区间和，时间複杂度是 O(H*W)。穷举所有矩形，同时确认矩形不含黑格子：判断矩形面积与区间和是否相等，就是 O((H*W)^2)。

简单的演算法

接著试试 Dynamic Programming 吧！

原来的纸张又大又複杂，计算面积非常麻烦。我们试著将纸张切成小块，逐一处理。这裡将纸张切成横条。

穷举纸张上的每个位置（穷举矩形右下角顶点），观察以上每个横条（穷举矩形高度），往左可延伸的长度（预先用 Largest Empty Interval 得到矩形宽度），持续记录最大矩形面积。

时间複杂度分析：一、每个横条计算 Largest Empty Interval。二、穷举矩形右下角顶点，穷举矩形高度，计算矩形面积。时间複杂度是 O((H*W)*H)。

空间複杂度分析：储存全部问题的答案，空间複杂度是 O(H*W)。只想计算一个特定问题的答案，空间複杂度仍是 O(H*W)。

可以改为切直条。可以改为穷举矩形右上角顶点。道理都一样。

程式码

为了不超出边界、导致溢位，于是在纸张外面多围一圈。这是实作二维地图的常见手法。

然后是一个横条的 Largest Empty Interval。

Largest Empty Square

Largest Empty Square

area(i, j) = min( area(i-1, j), area(i-1, j-1), area(i, j-1) ) + 1

穷举纸张上的每个位置，做为正方形右下角，计算正方形面积：看看正方形的右上角、左上角、左下角最远到哪裡。

时间複杂度为 O(H*W)，空间複杂度为 O(min(H, W))。

UVa 10908

Maximum Sum Subarray

Maximum Sum Subarray

2 -7  4 -3  6  4 -4  1 -5 0
      \______  ______/
             \/
             8

总和最大的区间。从数列当中取出一连串数字，求总和；找出最大的总和。最糟糕的情况，就是不取任何数字，总和为零。

可能不只一种。

穷举法。穷举区间起点、区间终点，计算总和。时间複杂度是 O(N^3)。

贪心法。累计总和，遇到负数就捨弃。时间複杂度是 O(N)。

UVa 507 10684

Maximum Sum Submatrix

这个问题还可推广到 2D、3D，时间複杂度分别是 O(N^3)、O(N^5)。原理是面与面合併，条与条合併，元素与元素合併。以下直接提供 3D 的情形。

Maximum Average Subarray

Maximum Average Subarray（Maximum Density Segment）

区间总和除以区间长度，平均值最大的区间。

直接法。当数列没有正数，则区间长度是 0。当数列有正数，区间长度越小，平均值越大；区间长度是 1，平均值最大，位于数列最大值。时间複杂度 O(N)。

计算几何。计算前缀和 P[i]，可快速求得区间[i, j]的平均值(P[i] - P[j-1]) / (i - (j-1))。进一步想成：数对(i, P[i]) 与数对(j-1, P[j-1]) 相减后算 y/x！

原问题变成：点集合(i, P[i]) 与点集合(-i, -P[i]) 的 Pairwise Sum 当中，求 y/x 最大者。一定位于凸包的顶点。

凸包有著很快的演算法。将 Pairwise Sum 拓展成 Minkowski Sum，改以多边形的观点来看问题。两个多边形的 Minkowski Sum 的凸包，就是两个多边形的凸包的 Minkowski Sum。得到简洁的演算法：求(i, P[i]) 的凸包，求(-i, -P[i]) 的凸包，求 Minkowski Sum，找到 y/x 最大的顶点。时间複杂度 O(N)。

Maximum Average Subarray with Length K

滑动视窗，O(N)。

Maximum Average Subarray with Length [L, R]

不能是空区间。总和为正数，区间越短越有利；总和为负数，区间越长越有利。

穷举法。穷举区间起点、区间终点，求平均。时间複杂度 O(N^3)。

试误法。穷举区间长度，求符合长度的 Maximum Average Subarray，滑动视窗。时间複杂度 O(N^2)。

试误法。二分搜寻平均值，总共 logR 个回合。针对一种平均值，所有数字皆减去平均值，求 Maximum Sum Subarray。若是空区间，则平均值须更大；若非空区间，则平均值可更小。时间複杂度 O(NlogR)。

计算几何。建构二维座标系，索引值为 X 轴，前缀和为 Y 轴，(i, P[i]) 为 N 个座标点，区间即线段，区间平均值即线段斜率，平均值最大的区间即斜率最大的线段。

套用“ Sweep Line ”，先穷举区间右边界，再穷举区间左边界。斜率最大的线段，就是右端点到左方所有点的下切线！换句话说，就是右端点到左方所有点的凸包的下切线！

改为套用“ Andrew's Monotone Chain ”，只求下凸包。建立 stack，逐次加入一点，找到下切线，更新凸包。所有下切线当中，斜率最大者，即为答案。时间複杂度 O(N)。

区间拥有宽度限制时，只求该范围的下凸包。

宽度下限：额外的新下切线做为答案。

宽度上限：困难处在于删除下凸包的最左侧顶点，并且快速地重新包覆。解决方法是预计算：上述演算法事先从右到左扫描，求得下凸包的演变过程，反过来运作，就是删除了。

ICPC 4726 3716