题目
分析
如果用暴力法求解，那么复杂度会太高。对于一个n * n的矩阵来说，起始行列有两个循环，终止行列有两个循环。然后要对这个“小”矩形内的元素求和：又是一个双重循环。所以总的时间复杂度来到了\(O(N^6)\)——太过分了。
结合之前的前缀和思路，我们需要设法保留“之前”的和，然后再加新的元素。对于一个矩形来说，比较自然的思路是：
- 限定起始行、终止行。这确定了求权子矩阵的上下边界。这是一个双重循环。
- 对于从左到右的每一列，可以借用前缀和的思路：只要算出上下边界中当前列的元素和，加上之前的前缀和就能得到新的和。但实际应用中，可以简单循环求和。
for (int top = 0; top < n; ++top)
{
fill(col.begin(), col.end(), 0);
for (int bottom = top; bottom < n; ++bottom)
{
//算出top-bottom行间，各个col的总和
for (int j = 0; j < n; ++j)
{
col[j] += a[bottom][j];
}
// ... ...
}
}
如果想象一下，这有点“将一个二维矩阵压缩到了一个一维向量”的感觉。这样的“降维”思路很重要，值得牢记。
最值的追踪
一般而言，不是每次都要加上本列以及之前列的前缀和才会使总和更大——如果是这样，这道题目就没有意义了，因为最大和必然是整个矩阵的元素和。
是否要加上本列，有一个简单的判定：如果本列的和为负数，那么不加本列更好。这个判定在两个方向上都是成立的：
- 之前的前缀和是正数，不要加本列。
- 本列为负数，但后面一列是正数，那么从下一列开始更好。
以样本数据为例，可以清楚地看到这个判定是适用的。
0 –2 –7 0
9 2 –6 2
-4 1 –4 1
-1 8 0 –2如此，在上下限确定的前提下，我们遍历所有的列，一定能找到在该上下限下最好的列组合以及最值。
然后不断调整上下限，得到最终的最值。
这个算法是\(O(N^3)\)。
核心代码是：
// 简单算出每列在top-bottom期间的和
for (int j = 0; j < n; ++j)
{
col[j] += a[bottom][j];
}
// Kadane on col[], handle all-negative correctly
long long cur = col[0], best = col[0];
for (int j = 1; j < n; ++j)
{
// 要么从当前列重新开始（col[j]），
// 要么接在之前的区间后面（cur + col[j]）
cur = max(col[j], cur + col[j]);
best = max(best, cur);
}
ans = max(ans, best); //更新当前区间最值答案
思考
这里我们用到了Kadane算法。有兴趣的读者可以参考这篇文章的介绍。
简单地说，它用两个变量跟踪最值情况：
cur：到当前列（j）的最值，考虑了加还是不加本列的情形。best：跟踪当前top-bottom区间的最值。