POJ1050To the Max（求最大子矩阵）

题意：给出N*N的矩阵，求一个子矩阵使得子矩阵中元素和最大

分析：

必备知识：求一组数的最大连续和

 1    int a[N];
 2    int sum = 0,maxn = -INF;
 3    for(int i = 1; i <= n; i++)
 4    {
 5         if(sum + a[i] > a[i])
 6             sum += a[i];
 7         else
 8             sum = a[i];
 9         maxn = max(sum, maxn);
10    }

一维数组最大连续和

假设要求的子矩阵位于 r 行到 i 行，c 列到 j 列之间怎么找出这个值呢？

方法：可以讲矩阵从 r 行到 i 行之间按照列求和放到一个数组中，colsum[y] 表示 y 列所有元素的和，所以对这个colsum[] 来求最大连续和就得出解来

但是不知道最大子矩阵是位于那两个行之间，需要两重循环枚举r 行到 i 行

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 const int Max = 210;
 7 const int INF = 0x3f3f3f3f;
 8 int matrix[Max][Max];
 9 int colsum[Max],n,maxn;
10 int maxcolsum()
11 {
12     int ans = 0, colmax = -INF;
13     for(int i = 1; i <= n; i++)
14     {
15         if(colsum[i] + ans > colsum[i])
16             ans += colsum[i];
17         else
18             ans = colsum[i];
19         if(colmax < ans)
20             colmax = ans;
21     }
22     return colmax;
23 }
24 int maxMatrix()
25 {
26     for(int i = 1; i <= n; i++)
27     {
28         memset(colsum, 0, sizeof(colsum));
29         for(int j = i; j <= n; j++)
30         {
31             for(int k = 1; k <= n; k++)
32                 colsum[k] += matrix[j][k];  //求 从 i 行到 j 行所有的列元素的和
33             int ans = maxcolsum();  // 对列元素和 求 最大连续和  
34             if(maxn < ans)
35                 maxn = ans;
36         }
37     }
38     return maxn;
39 }
40 int main()
41 {
42 
43     while (scanf("%d", &n) != EOF)
44     {
45         for(int i = 1; i <= n; i++)
46             for(int j = 1; j <= n; j++)
47                 scanf("%d", &matrix[i][j]);
48         maxn = -INF;
49         printf("%d
",maxMatrix());
50     }
51     return 0;
52 }

View Code