wwldx @ 2020-05-13 20:50:57
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1000000007;
const int maxn=155;
const int inf=0x3f3f3f3f;
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
#define ms(a) memset(a,0,sizeof(a))
#define mss(a) memset(a,-1,sizeof(a))
#define msi(a) memset(a,inf,sizeof(a))
// head
ll a[maxn][maxn];
ll b[maxn];
ll dp[maxn];
ll maxx=-inf,n;
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
cin>>n;
rep(i,1,n+1)
rep(j,1,n+1)
{
cin>>a[i][j];
}
// 压缩 1-1 1-2 1-3 1-4 2-2 2-3 2-4 3-3 3-4 4-4
// n*(n+1)/2
rep(i,1,n+1)
{
rep(j,i,n+1)
{
// b[z]=0;
rep(z,1,n+1)
{
b[z]+=a[j][z];
// b[z]+=b[z-1];
}
}//压缩
//长度为n的串,找最大子段和
rep(z,1,n+1)
{
// maxx=max(maxx,b[z-1]+b[z]);
b[z]=max(b[z],b[z-1]+b[z]);
// dp[z]=max(dp[z-1]+b[z],b[z]);
maxx=max(b[z],maxx);
// b[z-1]=0;
}
// b[n]=0;
memset(b,0,sizeof(b));
// memset(dp,0,sizeof(dp));
}
cout<<maxx<<"\n";
return 0;
}
by wlxs2006 @ 2020-05-13 21:10:50
(⊙o⊙)…