这对uva108来说仅仅是增加一个条件：可以越过边界。
大多数网上的解法
这题是108的变形，网上大多数的解法是：
用一个4N^2 大小的矩阵来存储原来矩阵。
模拟左上角点的坐标O(N^2) * 控制小矩形的长度O(N) * 最大连续子序列和O(N) => O(N^4)
最大连续子序列和
顺带着，这道题和108都用到了 最大连续子序列和 ，关于这个就有好多种解法。 这里就来讲一下关于O(NlogN)和O(N)算法的理解。
-
基本的分治： 获得左右2边的max值;
合并：求出包含中间元素的一块区域的max值。取三者最大值即可。
由于分治能够很简单的用数学归纳法证明，故不再述。
-
$S_i = a_0 + a_1 + \cdots + a_i$, 则最大连续子序列可以表示为$S_i - S_j (i>j)$, 若$S_i$不变，则只要$S_j$为最小，则所求值即可达到最大;而维护当前最小的S只需要O(N)的复杂度。(没错，这个就是lrj书本上写着的)
int s[n];
s[0] = a[0];
for (int i = 1; i < n; ++i)
s[i] = s[i - 1] + a[i];
int smin = a[0];
int _max = a[0];
for (int i = 0; i < n; ++i) {
if (smin > s[i])
smin = s[i];
if (_max < s[i] - smin)
_max = s[i] - smin;
}
- 利用dp的思想（$F_i$ 可以是上一次的延续或者是这一次的开始）可以写出如下的状态转移方程：
-
分析一下，你就知道。
从多个运行结果可以看出来，所找到的最大连续子序列的头1个数必定是正的。
假设是负的，则可以将负的去掉，从而得到的序列肯定比以前的要大，所以可以采取这个策略。
PS: 以前一直是这样写的:
int s = 0, r = 0;
for (int i = 0; i < n; ++i) {
s += a[i];
if (s > r)
r = s;
else if (s < 0)
s = 0;
}
后来发现太有局限性了，改成了
int s = 0, r = a[0];
for (int i = 0; i < n; ++i) {
s += a[i];
if (s > r)
r = s;
else if (s < 0)
s = 0;
}
显然可以看出对于『-3, -2, -1』不成立，问题在于当s小于0时没有及时的清零。
最终可以改成
int s = 0, r = a[0];
for (int i = 0; i < n; ++i) {
s += a[i];
if (s > r)
r = s;
if (s < 0)
s = 0;
}
或者是这种
int s = 0, r = a[0];
for (int i = 0; i < n; ++i) {
s = (s > 0 ? s + a[i] : a[i]);
if (s > r)
r = s;
}
关于本题
至此，本题的解法还没有说唉！
令\(s_{i,j}\)代表\(a_{0,j}, a_{1,j}, \cdots, a_{i,j}\)的和，则在x行与y行之间的值可以表示为\(s_{y,0} - s_{x,0}; s_{y,1} - s_{x,1}; \cdots\)
而找1个和最大的矩形块即是在上面创建的数组中找一个最大连续子序列和。
先考虑只有左右2边可以越过边界时，这2种情况是：
- 产生的最大值不跨边界，则可以直接应用最大连续子序列和算法过。
- 跨界了，即只空出中间一块，由于要满足最大连续子序列和的性质，则中间未被选中的是最小的，即可求出中部的最小连续子序列和，再取个补即可。
现在已经解决左右2边可以越过边界的情况，只差上下2边了。 此时，可以将原矩形向下N单位复制一份，再应用上述的方法;或者可以将额外空间减小至O(N), 像他一样将过程全部展开，而节省空间，不过可读性就…23333