题目描述

n^3算法

C++ 代码

include[HTML_REMOVED]

using namespace std;
int n,sum[105][105],ans,f=0,mi=INT_MIN;
int main(){
cin>>n;
for(int i=1;i<=n;i)
for(int j=1;j<=n;j)
{
cin>>sum[i][j];
mi=max(mi,sum[i][j]);
}
if(mi>0)
{
for(int j=1;j<=n;j)
for(int i=1;i<=n;i)
sum[i][j]+=sum[i-1][j];
for(int u=1;u<=n;u)
for(int d=u;d<=n;d)
{
int s=0;
for(int j=1;j<=n;j++)
{ans=max(ans,s);s+=sum[d][j]-sum[u-1][j];if(s<=0)s=0;}
//cout<<s<<endl;
ans=max(ans,s);
}
cout<<ans<<endl;
}
else {
cout<<mi<<endl;
}

return 0;

}