百练oj 2766 最大子矩阵和

 1 #include<stdio.h>
 2 #include<string.h>
 3 int a[110][110],n;
 4 int maxx(int *b,int m)
 5 {
 6     int i,max,now;
 7     for(i=0;i<m;i++)
 8     {
 9         if(i==0)
10         {
11          now=max=b[i];
12          continue;
13         }
14         if(now+b[i]>b[i])
15         now+=b[i];
16         else now=b[i];
17         if(max<now)
18         max=now;
19     }
20     return max;//计算不同的行之间的相同的列之和的最大和，即一个矩阵 
21 }
22 int maxpp()
23 {
24     int b[11111],i,j,sum=-999999,max,k;
25     for(i=0;i<n;i++)//将所有的行枚举一遍 
26     {
27        memset(b,0,sizeof(b));
28        for(j=i;j<n;j++)//这里仿造最大字段和的写法 
29        {
30          for(k=0;k<n;k++)
31          { 
32            b[k]+=a[j][k];//b[k]为纵向的列的和，这样每个b[k]对应的行，列就都一样了，就可以进行相加比较了 
33            max=maxx(b,k+1);
34            if(sum<max)sum=max;//这三行之所以放在同一的循环里面就是为了 每一纵列都能进行一次取最大值
35          } 
36        }     
37     }
38     return sum;
39 }
40 int main()
41 {
42     int i,j;
43     while(scanf("%d",&n)!=EOF)
44     {
45        for(i=0;i<n;i++)
46          for(j=0;j<n;j++)
47            scanf("%d",&a[i][j]);
48        printf("%d\n",maxpp());
49     }
50     return 0;
51 }