一、题意

输出n，然后输入一个n*n（n<=100）的数字矩形，要求你找出这个矩形中数字和最大的子矩形。
输出这个子矩形的数字和。

二、解析

先来回顾一下一维的最大连续子数列和问题：在一个长度为n的数列a[1...n]中，找到数字和最大的子序列。
在一维情形我们有4种方法：

  • 方法一：暴力枚举，枚举子序列首尾，然后求和，复杂度O(n^3)，绝对不会用的方法。
  • 方法二：通过维护sum[i]=sum(a[1..i])数组，将时间复杂度降到O(n^2)，但依然不完美。
  • 方法三：动态规划。dp[i]=max(a[i], dp[i-1]+a[i])，其中dp[i]表示以第i位数字为结尾的子序列的最大连续和，它要么就是一个最大子序列的开头，要么就接着作为dp[i-1]的延续。最终答案就是max(dp[i])，时间复杂度仅为O(n)。完美。
  • 方法四：由于最大连续和一定是sum[i]-sum[j]，其中sum[j]是sum[0]...sum[i-1]中最小的那个，因此只需要边求sum边维护最小值即可。用时也是O(n)。同样完美。

个人比较喜欢用动态规划的方法。

回到这道题，上述的方法就能给我们一些思路，最终通过尝试发现，方法二能够比较完美的转化为二维的方法，但同时还要结合动态规划的思想：dp[i][j]表示以a[i][j]为右下角的子矩形中的最小数字和，sum[i][j]表示以a[i][j]为右下角的最大矩形的数字和；则dp[i][j]=max(dp[i][j], sum[i][j] - sum[li][j] - sum[i][lj] + sum[li][lj])，即枚举子矩形左上角的位置。

这样时间复杂度为O(n^4)，考虑到n<=100，因此不会超时。

三、代码

#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 100 + 5, INF = 1 << 30;
int n, a[maxn][maxn], sum[maxn][maxn], dp[maxn][maxn];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) cin >> a[i][j];
    int ans = -INF;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
            dp[i][j] = -INF;

            for(int li = 0; li < i; li ++) {
                for(int lj = 0; lj < j; lj ++) {
                    dp[i][j] = max(dp[i][j], sum[i][j] - sum[li][j] - sum[i][lj] + sum[li][lj]);
                    ans = max(ans, dp[i][j]);
                }
            }
        }
    }
    cout << ans << endl;
}

四、归纳

  • 这里的矩形动态规划用到了一个小技巧：从a[1][1]开始填充数字，即将第0行和第0列留空为0.这样的好处是进行dp时不需要特意初始化这两行了，可以直接从a[1][1]开始dp，从而减少代码量。