1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2+5;
const int inf = 0x7fffffff;

int f[maxn][maxn][maxn];
/* 
 * pre_sum[i][j] 第i列,j个元素
 * i : 列
 * j : 行
 * */
int pre_sum[maxn][maxn];
int _map[maxn][maxn];
int n;

void init(){
    scanf("%d",&n);
    int i,j,k;
    memset(pre_sum,0,sizeof(pre_sum));
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            scanf("%d",&_map[i][j]);
        }
    }

    for(j=1;j<=n;j++){ //列
        for(i=1;i<=n;i++){ //行
            pre_sum[i][j] = pre_sum[i][j-1] + _map[j][i];
        }
    }
}

/* i:第i 行 开始
 * j: 第j行 结束
 * k: 第k列
 * */
int sum(int i,int j ,int k){
    return pre_sum[k][j] - pre_sum[k][i-1];
}

int main(){
    init();
    int i,j,k;
    int ans = -inf;

    for(i=1;i<=n;i++){
        for(j=i;j<=n;j++){
            for(k=1;k<=n;k++){
                if(f[i][j][k-1] >= 0){
                    f[i][j][k] = f[i][j][k-1] +sum(i,j,k);
                }
                else
                    f[i][j][k] = sum(i,j,k);
                ans = max(f[i][j][k],ans);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}