思路

最朴素的想法是枚举左上角和右下角，要用 $4$ 个 for 循环，加上二维前缀和，复杂度 $O(n^4)$。

我们进行优化：

枚举边界，如下图所示：边界 $1$、边界 $2$ 和边界 $3$ 就是枚举的边界。

把边界 $1$ 和边界 $2$ 之间的每一列看做一个整体（图中的相同颜色），每个整体的值就是这些元素的累加和，我们枚举边界 $3$，找出一边界 $3$ 作为右边界的最优矩形。

找矩形的方法：

假设有数组 $a$，我们用 $f_i$ 表示已 $i$ 为终点的最大连续和。

• 如果 $f_{i - 1} > 0$，$f_i = a_i + f_{i - 1}$；
• 如果 $f_{i - 1} \leq 0$，$f_i = a_i$。

我们可以用前缀和求出整体的累加和，然后再用上面求 $f$ 数组的方法求出最优矩形。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 110;

long long a[N][N];

int main()
{
    long long n, ans = -0x3f3f3f3f;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> a[i][j];
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            a[i][j] += a[i - 1][j];
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j ++ )
        {
            long long sum = 0;
            for (int k = 1; k <= n; k ++ )
            {
                sum = max(sum, 0ll) + a[j][k] - a[i - 1][k];
                ans = max(ans, sum);
            }
        }
    cout << ans << endl;
    return 0;
}