结对开发2----最大子矩阵

  1 #include <iostream>  
  2 
  3 #include <vector>  
  4 
  5 using namespace std;  
  6 
  7    
  8 
  9 const int N = 101;  
 10 
 11 int a[N][N], p[N][N];  
 12 
 13    
 14 
 15 int MaxRecSum(int n)  
 16 
 17 {  
 18 
 19     for (int i = 0; i <= n; ++i)  
 20 
 21     {  
 22 
 23         p[i][0] = 0;  
 24 
 25         p[0][i] = 0;  
 26 
 27     }     
 28 
 29     for ( i = 1; i <= n; ++i)  
 30 
 31     {  
 32 
 33         for (int j = 1; j <= n; ++j)  
 34 
 35             p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j];  
 36 
 37     }  
 38 
 39    
 40 
 41     int max = INT_MIN;  
 42 
 43     for ( i = 1; i <= n; ++i)  
 44 
 45     {  
 46 
 47         for (int j = i; j <= n; ++j)  
 48 
 49         {  
 50 
 51             int sum = 0;  
 52 
 53             for (int k = 1; k <= n; ++k)  
 54 
 55             {  
 56 
 57                 int temp = p[j][k] - p[j][k-1] - p[i-1][k] + p[i-1][k-1];  
 58 
 59                 if (sum > 0)  
 60 
 61                     sum += temp;  
 62 
 63                 else 
 64 
 65                     sum = temp;  
 66 
 67                 if (sum > max)  
 68 
 69                     max = sum;  
 70 
 71             }  
 72 
 73         }  
 74 
 75     }  
 76 
 77     return max;  
 78 
 79 }  
 80 
 81    
 82 
 83 int main()  
 84 
 85 {  
 86 
 87     int n = 3;  
 88 
 89     int num;  
 90 
 91     cout<<"矩阵的规格为三行三列，请输入数值："<<endl;
 92 
 93     for (int i = 1; i <= n; ++i)  
 94 
 95     {  
 96 
 97         for (int j = 1; j <= n; ++j)  
 98 
 99         {  
100 
101             cin >> num;  
102 
103             a[i][j] = num;  
104 
105         }  
106 
107     }  
108 
109       
110 
111    
112 
113     cout <<"最大字矩阵的和为："<< MaxRecSum(n) << endl;  
114 
115      
116 
117     for ( i = 1; i <= n; ++i)  
118 
119     {  
120 
121         for (int j = 1; j <= n; ++j)  
122 
123         {  
124 
125             cout <<a[i][j]<<"   "; 
126 
127         }  
128 
129         cout<<endl;
130 
131     }  
132 
133     return 0;  
134 
135 }