最大字段和题型,推荐做题顺序:
HDU1003
HDU1024
HDU1081
ZOJ2975
ZOJ2067
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
using namespace std;
int n,a[][];
int y[],maxp[];
int Max;
int main()
{
int i,j,k;
while(~scanf("%d",&n)){
for(i=;i<=n;i++)
for(j=;j<=n;j++)
scanf("%d",&a[i][j]);
Max=a[][];
for(i=;i<=n;i++)
{
memset(y,,sizeof(y));
memset(maxp,,sizeof(maxp));
for(j=i;j<=n;j++)
{
for(k=;k<=n;k++){
y[k]+=a[j][k];
maxp[k]=y[k];
maxp[k]=max(maxp[k-]+y[k],maxp[k]);
Max=max(Max,maxp[k]);
}
}
}
printf("%d\n",Max);
}
return ;
}