Posted on 2012-02-24 16:58
C小加 阅读(331)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
a[i][j]=a[i-1][j]+among;这样存值的话就可以转化成求 和最大连续子串
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=0x7fffffff-1;
int a[103][103];
int main()
{
memset(a,0,
sizeof(a));
int n,among;
while(scanf("%d",&n)!=EOF)
{
for(
int i=1;i<=n;i++)
for(
int j=1;j<=n;j++)
{
scanf("%d",&among);
a[i][j]=a[i-1][j]+among;
}
int ans=-INF;
for(
int i=0;i<n;i++)
{
for(
int j=i+1;j<=n;j++)
{
int maxnum=a[j][1]-a[i][1];
ans=max(maxnum,ans);
for(
int k=2;k<=n;k++)
{
if(a[j][k]-a[i][k]+maxnum<a[j][k]-a[i][k])
{
maxnum=a[j][k]-a[i][k];
ans=max(maxnum,ans);
}
else {
maxnum+=a[j][k]-a[i][k];
ans=max(maxnum,ans);
}
}
}
}
printf("%d\n",ans);
}
return 0;
}