#include<stdio.h>
#include<stdlib.h>
int sumofsubrect(int **s, int r1, int c1, int r2, int c2)
{
	int sum=0,i,j;
	for(i=r1;i<=r2;i++)
		for(j=c1;j<=c2;j++)
			sum=sum+s[i][j];
		return sum;
}
int main()
{
	int i,j,n,max,r,c,temp,okmax,**s;
	scanf("%d",&n);
	s=(int**)malloc(n*sizeof(int*));
	for(i=0;i<n;i++)
		s[i]=(int*)malloc(n*sizeof(int));
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			scanf("%d",&s[i][j]);
		okmax=s[0][0];
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			max=s[i][j];
			for(r=0;r<=i;r++)
				for(c=0;c<=j;c++)
				{
					temp=sumofsubrect(s,r,c,i,j);
					if(temp>max)
						max=temp;
				}
					if(max>okmax)
						okmax=max;
		}
				printf("%d\n",okmax);
	return 1;
}

• I think you should learn "integral image" instead of DP (0) gongml 2005-10-10 06:18:22
  • Re:I think you should learn "integral image" instead of DP (0) eleapple 2005-10-10 17:13:44
    • Think you for your hint ,I conquer it under you help (16) eleapple 2005-10-10 17:18:51
      • Wow, so quickly... (0) gongml 2005-10-10 21:04:01