分别枚举矩形的上下边,把问题转化为求一维的最大子段。
#include<iostream>
using namespace std;
int arr[105][105];
int n,t[105];
const int inf=100000000;
int maxsubr()
{
int maxn=-inf,sum=0;
for(int i=1;i<=n;i++)
{
if(sum>0)
sum+=t[i];
else
sum=t[i];
if(maxn<sum)
maxn=sum;
}
return maxn;
}
int main()
{
int i,j;
int ans=-inf;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&arr[i][j]);
for(i=1;i<=n;i++)
{
memset(t,0,sizeof(t));
for(j=i;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
t[k]+=arr[j][k];
}
int temp=maxsubr();
if(ans<temp) ans=temp;
}
}
printf("%d\n",ans);
return 0;
}
posted on 2010-08-11 10:19
wuxu 阅读(112)
评论(0) 编辑 收藏 引用 所属分类:
动态规划