最大子矩阵和

/*
 * @Author      : YaleXin
 * @Email       : me@yalexin.top
 * @LastEditors : YaleXin
 */
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int num[101][101], sums[101][101], temp[101];
int n;
int oneMatMaxSum(){
    int nowSum = 0, maxSum = -128 * 100 - 1;
    for(int i = 0; i < n;i++){
        if (nowSum > 0)nowSum += temp[i];
        else nowSum = temp[i];
        maxSum = max(maxSum, nowSum);
    }
    return maxSum;
}
// 给出一个方阵  求最大子矩阵和
int main() {
    ios::sync_with_stdio(false);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            scanf("%d", &num[i][j]);
            sums[i][j] = num[i][j];
        }
    for (int i = 1; i < n; i++) 
        for (int j = 0; j < n; j++)
            sums[i][j] += sums[i - 1][j];
    int maxSum = -128, nowSum;
    for (int i = 0; i < n; i++){
        for (int j = i; j < n; j++){
            // temp 保存的是从 第 i 行到 第 j 行所对应的矩阵每一列的和
            for (int k  = 0; k < n;k++){
                if (i == 0)temp[k] = sums[j][k];
                else temp[k] = sums[j][k] - sums[i - 1][k];
            }
            nowSum = oneMatMaxSum();
            maxSum = max(nowSum, maxSum);
        }
    }
    cout << maxSum << endl;
    return 0;
}