虽然是一道橙题，但还是蕴含了重要算法思想——降维思想。
如果是一维形式，即最大子段和，我们采取先求前缀和，并固定右端点，减去左边最小的办法求。
对于这题，若固定了上下边界，则可以利用列的前缀和将其“压缩”为一维形式，再采取“最大子段和”的方式求解。
如下面一个二维矩阵：
1 2 3 4
-1 3 4 10
9 10 8 6
可以压缩成如下一维形式：
9 15 15 20
便可以在 \(O(n)\) 内求解。
算上固定上下边界，总时间复杂度就是 \(O(n^3)\)
CODE：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read() {
LL sum=0,flag=1; char c=getchar();
while(c<'0'||c>'9') { if(c=='-') flag=-1; c=getchar(); }
while(c>='0'&&c<='9') { sum=sum*10+c-'0'; c=getchar(); }
return sum*flag;
}
const int N=150;
int n,ans=-1e9;
int a[N][N],sum[N][N],f[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 j=1;j<=n;j++) {
for(int i=1;i<=n;i++) {
sum[i][j]=sum[i-1][j]+a[i][j];
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=i;j++) {
for(int z=1;z<=n;z++) {
int val=sum[i][z]-sum[j-1][z];
f[z]=max(val,f[z-1]+val);
ans=max(ans,f[z]);
}
// ans=max(ans,f[n]);
}
}
cout<<ans<<endl;
return 0;
}