最大子阵和

题目描述

有一个包含正数和负数的二维数组。一个子矩阵是指在该二维数组里，任意相邻的下标是1*1或更大的子数组。一个子矩阵的和是指该子矩阵中所有元素的和。本题中，把具有最大和的子矩阵称为最大子矩阵。

例如：

0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2

这个数组的最大子矩阵为：

9 2

代码：

-4 1

-1 8

其和为15。

#include <bits/stdc++.h>  
#define CLR(x,y) memset((x),y,sizeof(x)) 

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int seed = 131;
const int maxn = 1e5 + 5;
const int mod = 998244353;
int a[105][105];
int b[105];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    int MAX = -99999;
    for (int i = 1; i <= n; i++) {
        CLR(b, 0);
        for (int j = i; j <= n; j++) {
            int sum = 0;
            for (int k = 1; k <= n; k++) {
                b[k] += a[j][k];
                sum += b[k];
                if (sum < 0) sum = b[k];
                MAX = max(MAX, sum);
            }
        }
    }
    printf("%d\n", MAX);
    return 0;
}