给定一个\(N \times N (N \le 100)\)的矩阵,找到最大子矩阵和。

链接: 题目UVa






题解

首先想到暴力,复杂度\(O(N^6)\),肯定超时。

然后有一种\(O(N^4)\)的解法,AC足够了。

但是可以通过把二维矩阵压到一维,复杂度\(O(N^3)\)的解。看题解2哟。

题解 1

用数组sum保存自原矩阵左上角到右下角坐标为\(i, j)\)该区域内所有数的和。

如下图所示,显然有 $$ \begin{align} A &= (A+B+C+D)\\ &-(B+D)\\ &-(C+D)\\ &+D \end{align} $$ 所以我们可以得到 A = sum[k][l] - sum[i-1][l] - sum[j-1][k] + sum[i-1][j-1]

max_sum

有个小技巧, 保存数组从 index 1 开始,初始化数组为 0 。这样可以省略边界处理。一开始样例都调不出来,找不到原因。后来发现我在 for 循环里用了 < 而不是 <=.

#include<iostream>
#include<algorithm>
#define maxn 100+5
using namespace std;
int v, N, sum[maxn][maxn] = 0;

void solve() {
    int MaxSum = -200;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = i; k <= N; k++) {
                for (int l = j; l <= N; l++) {
                    MaxSum = max(MaxSum, sum[k][l]-sum[i-1][l]-sum[k][j-1]+sum[i-1][j-1]);
                }
            }
        }
    }
    cout << MaxSum << endl;
}

int main(void) {
    while(cin >> N) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                cin >> v;
                sum[i][j] = v+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
            }
        }

        solve();
    }

    return 0;
}


Solution 2

在一维矩阵中,如果我们要找最大连续的区间和,状态转移方程如下: $$ d[k] = max(d[k-1]+d[k], d[k])$$ 有一个小优化就是根据贪心,我们知道如果当前的和小于0,就没有再使用它的意义了。因为加一个小于零的数肯定会减小和。

当我们知道了如何在一维中寻找最大连续区间的和,在二维中就很容易了。

i = 开始行数
j = 结束行数,有i <= j
k = 列数

我们可以把在 ij 之间的所有行,以列的方式相加,储存到一维数组相应的角标下。

这样,这题就变成了一维数组求最大连续区间和了。找到的该和就是原二维数组中的长方形内所有数字的和。

max_sum_2d

#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 100+5
using namespace std;
int N, m[maxn][maxn], x[maxn];

int find_max() {
    int cur_sum=x[0], sum=0;
    for (int l = 0; l < N; l++) {
        sum += x[l];
        cur_sum = max(sum, cur_sum);
        if (sum < 0) sum = 0;
    }
    return cur_sum;
}

void solve() {
    int MaxSum = -200;
    for (int i = 0; i < N; i++) {
        memset(x, 0, sizeof(x));
        for (int j = i; j < N; j++) {
            for (int k = 0; k < N; k++) x[k] += m[j][k];
            MaxSum = max(MaxSum, find_max());
        }
    }
    cout << MaxSum << endl;
}

int main(void) {
    while(cin >> N) {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                cin >> m[i][j];
        solve();
    }

    return 0;
}