二维前缀和的扩展

如果说，这题用一个预处理一个二维前缀和，然后枚举子矩阵的左上角与右上角，那么我们可以用$O(n^4)O(n^4)$的时间复杂度得到答案。不过对于这题n=100来说，$100^4=10^{8}100^4=10^8$会超时。

所以我们要想办法优化，最蛋疼的点其实在于暴力的枚举会涉及非常多无用的状态。我们可以优化枚举，转而变成枚举上界与下界。

类似这样，两条红线是我们枚举的上下界。那么问题来了，如何快速的得到两条红线夹出来的子矩阵里的最大子矩阵？（我称之为子子矩阵）

我们可以考虑这个问题的简化版。如果快速得到一个序列里的最大子序列和？这是一个经典的线性dp问题，可以用$O(n)O(n)$时间复杂度解决。我们这简化问题迁移到原问题上面来，这样一个子矩阵里的最大子子矩阵，要套用简化问题里的dp方程，我们必须得首先把整个列压缩成一个元素。（把一列看成一个元素，那么整个矩形就被压缩成了一个序列）而这启发我们在列上做一个前缀和。

只要在列上做了一个前缀和，那么我们就可以直接套用最大子序和的dp方程来$O(n)O(n)$得到最大子子矩阵。而枚举子矩阵是用两条红线来枚举的，时间复杂度是$O(n^2)O(n^2)$。因此总的时间复杂度就是$O(n^3)O(n^3)$。

#include <iostream>

using namespace std;

const int N = 110;

int n;
int grid[N][N];
int s[N][N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &grid[i][j]);
    
    //做一个列方向上的前缀和
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            s[i][j] = s[i - 1][j] + grid[i][j];
    
    int res = -1e9;
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
        {
            int f = 0; //进行最大子序列和的dp
            for (int k = 1; k <= n; ++k)
            {
                int w = s[j][k] - s[i - 1][k];
                f = max(0, f) + w;
                res = max(res, f);
            }
        }
    printf("%d\n", res);
    return 0;
}