题目描述

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是 )子矩阵。

比如，如下 的矩阵

0  -2 -7  0
9  2 -6  2
-4  1 -4  1
-1  8  0 -2

的最大子矩阵是

9 2
-4 1
-1 8

这个子矩阵的大小是15。

输入

输入是一个的矩阵。输入的第一行给出 。再后面的若干行中，依次(首先从左到右给出第一行的 个整数，再从左到右给出第二行的 个整数……)给出矩阵中的 个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在 。

输出

输出最大子矩阵的大小。

样例

输入样例

4
0 -2 -7  0
9  2 -6  2
-4  1 -4  1
-1  8  0 -2

输出样例

15

源代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int dp[101][101], arr[101];
int maxsub(int a[], int n) {
    int max = 0, b = 0;
    for (int i = 0; i <= n; i++) {
        if (b > 0)
            b += a[i];
        else
            b = a[i];
        if (b > max) max = b;
    }
    return max;
}
int main() {
    int n, maxx = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> dp[i][j];
    for (int i = 1; i <= n; i++) {
        memset(arr, 0, sizeof(arr));
        for (int j = i; j <= n; j++) {
            for (int k = 1; k <= n; k++) arr[k] += dp[j][k];
            int m = maxsub(arr, n);
            if (maxx < m) maxx = m;
        }
    }
    cout << maxx;
    return 0;
}

#include <cstdio>
#include <iostream>
using namespace std;
#define M 1000
int f[M][M], a[M][M];
int n, ans, maxn;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
            f[i][j] = f[i][j - 1] + a[i][j];
        }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            maxn = 0;
            for (int k = 1; k <= n; k++) {
                maxn += f[k][j] - f[k][i - 1];
                ans = max(maxn, ans);
                if (maxn < 0) maxn = 0;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

// Make sure to add code blocks to your code group