/**
* 首先计算每一列的前序和（即0行到所有行上值的总和）
* 其次，最大的子矩阵一定在a行和b行之间，所以我们可以枚举所有的可能组合，时间复杂度为O(N*N)
* 因为我们在第一步中计算了前序和，那么第二步中a行和b行之间的子矩阵可以看成一个一维的数组，长度为N。
* 其值的计算可以利用第一步中的前序和，遍历所有列，让0-b的总和减去0-a的总和，即为a-b的总和。
* 利用该算法算出该一维数组中的最大连续子序列。时间复杂度为O(N)，
* 找出最大值，最后的时间复杂度为0(N*N*N)。
*/
#include
#include
using namespace std;
#define MAX 101
#define INF 0x7fffffff
int array[MAX][MAX]; //矩阵数据
int arraySum[MAX][MAX+1]; //矩阵前序和
int tmp[MAX]; //临时一维数组
int n; //矩阵大小
/*
该算法十分简单，maxSum表示最终的最大值，currentMaxSum表示当前的最大值，只需要遍历数组一遍即可找出最大值。
*/
int findMaxinum(){
int maxSum = -INF, currentMax = 0;
for(int i=0; i
if(currentMax < 0) {currentMax = 0; continue;}
maxSum = max(maxSum, currentMax);
return maxSum;
}
int main(){
scanf("%d",&n);
for(int i=0; i
//计算前序和，i表示列，j表示最终行，总和为0-j上的所有值
for(int i=0; i
arraySum[i][j] = arraySum[i][j-1] + array[i][j-1];
int maxinum = -INF;
//遍历所有a，b的组合
for(int i=0; i
//计算临时一维数组
for(int x=0; x
}
maxinum = max(maxinum, findMaxinum());
}
}
printf("%d\n",maxinum);
return 0;
}