1785390_wa.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>

int MAX(int x,int y)
{
	return (x>y?x:y);
}
main()
{
  int n,i,j,k,l,sum,max = -128,t = -128,f[2][100][100],array[100][100];
 
  scanf("%d",&n);
  for(i = 0; i < n; i++)
  for(j = 0; j < n; j++)
  scanf("%d",&array[i][j]);
  
  for (i = 0; i < n;i++)
  for (j = i; j < n;j++)
  { 
   sum=0;
   for (k=i;k<=j;k++) sum+=array[1][k];
   f[0][i][j]=sum;
   }
  
  
      for(k = 1; k < n; k++)
	 {
	  for (i = 0; i < n; i++)
      for (j = i; j < n; j++)
       if (f[0][i][j]>t) t=f[0][i][j];
          if (t>max) max=t;	  
	  for(i = 0; i < n; i++)
      for(j = i; j < n; j++)
	  {
	    sum = 0;
         for(l = i; l <= j; l++) sum += array[k][l];
          f[1][i][j] = MAX(0,f[0][i][j])+sum;
	  }
       for (i = 0; i < n;i++)
       for (j = i; j < n;j++)
            f[0][i][j]=f[1][i][j];
	}
	  for (i = 0; i < n; i++)
      for (j = i; j < n; j++)
       if (f[0][i][j]>t) t=f[0][i][j];
          if (t>max) max=t;
  printf("%d\n",max); 
 
  return 0;
}