最大的和

AcWing-126-最大的和

分析

最大子矩阵和。

时间复杂度O(n​3​​)。

实现

#include <iostream>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 110;
int n, a[N][N];

int main () {
    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];
    
    int res = -inf;
    for (int i = 1; i <= n; ++ i) {
        for (int j = i; j <= n; ++ j) {
            int sum = 0;
            for (int k = 1; k <= n; ++ k) {
                sum += a[j][k] - a[i - 1][k];
                res = max(res, sum);
                if (sum < 0) sum = 0;
            }
        }
    }
    cout << res << endl;
    return 0;
}