最大子阵

 1 #include <iostream>
 2 #include <cstring>
 3 int maxSubArray(int* a,int n)//一维数组的最大和
 4 {
 5     if(!a||n<=0)
 6         return 0;
 7     int curmax=0,max=0;
 8     max=curmax=a[0];
 9     for(int i=1;i<n;i++)
10     {
11         if(curmax>=0)
12         {
13             curmax+=a[i];
14         }
15         else 
16             curmax=a[i];
17         if(curmax>max)
18             max=curmax;
19     }
20     return max;
21  } 
22 
23  int maxSumInMatrix(int a[200][200],int n)
24  {
25      int i=0,j=0,k=0;
26      int sumij[200]={0};//从i到j的每一列的和
27 
28      int max_n=a[0][0],max=a[0][0];
29 
30      for(i=0;i<n;i++)
31      {
32          memset(sumij,0,sizeof(sumij));//clear，每次移动i的时候清除
33          for(j=i;j<n;j++)
34          {
35 
36              for(k=0;k<n;k++)
37              {
38                  sumij[k]+=a[j][k];
39              }
40              max_n=maxSubArray(sumij,n);
41              if(max_n>max)//检查并更新最大值
42              max=max_n;
43          }         
44      }
45      return max;
46 }
47 
48  int main()
49  {
50      int a[200][200];
51      memset(a,0,sizeof(a));
52      int n;
53      std::cin>>n;
54      for(int i=0;i<n;i++)
55      {
56          for(int j=0;j<n;j++)
57          std::cin>>a[i][j];
58      }
59      std::cout<<maxSumInMatrix(a,n);
60  }
61 
62