最大子矩阵求和问题

朱雀 2022-09-17 12:23 154阅读 0赞

给定一个N\*N的矩阵，计算最大子矩阵和。

思路：

最大子段和问题可以用动态规划在O(n)内解决，该题可以借助最大子段和的解法来做。我们考虑第i行到第j行的子矩阵，可以将i ~ j行的矩阵合并为一个一维数组，即把每列对应的数相加，那么这个一维数组的最大子段和就是原子矩阵的最大和。

我们用一个二维数组p来保存矩阵的部分和，p\[i\]\[j\]表示左上角是(1, 1)，(下标从1开始)， 右下角是(i, j)的矩阵中元素的和。如果我们要求i~j行、k~m列的矩阵中元素的和，我们可以通过以下式子计算得出：

sum = p[j][m] - p[j][k-1] - p[i-1][m] + p[i-1][k-1]

只需要O(1)的时间。

部分和p\[i\]\[j\]要怎么计算呢？我们可以通过更小的部分和来计算得到它：

p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j]

其中a\[i\]\[j\]是矩阵中的整数。我们只需要O(n2 ) 的时间即可预处理得到所有的部分和。

所以总的时间为O(n3 )。

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  \#include <iostream>  
2.  \#include <vector>  
3.  using namespace std;  
4.    
5.  const int N = 101;  
6.  int a\[N\]\[N\], p\[N\]\[N\];  
7.    
8.  int MaxRecSum(int n)  
9.  \{  
10.     for (int i = 0; i <= n; ++i)  
11.     \{  
12.         p\[i\]\[0\] = 0;  
13.         p\[0\]\[i\] = 0;  
14.     \}     
15.     for (int i = 1; i <= n; ++i)  
16.     \{  
17.         for (int j = 1; j <= n; ++j)  
18.             p\[i\]\[j\] = p\[i-1\]\[j\] + p\[i\]\[j-1\] - p\[i-1\]\[j-1\] + a\[i\]\[j\];  
19.     \}  
20.   
21.     int max = INT\_MIN;  
22.     for (int i = 1; i <= n; ++i)  
23.     \{  
24.         for (int j = i; j <= n; ++j)  
25.         \{  
26.             int sum = 0;  
27.             for (int k = 1; k <= n; ++k)  
28.             \{  
29.                 int temp = p\[j\]\[k\] - p\[j\]\[k-1\] - p\[i-1\]\[k\] + p\[i-1\]\[k-1\];  
30.                 if (sum > 0)  
31.                     sum += temp;  
32.                 else  
33.                     sum = temp;  
34.                 if (sum > max)  
35.                     max = sum;  
36.             \}  
37.         \}  
38.     \}  
39.     return max;  
40. \}  
41.   
42. int main()  
43. \{  
44.     int n = 4;  
45.     int num;  
46.     for (int i = 1; i <= n; ++i)  
47.     \{  
48.         for (int j = 1; j <= n; ++j)  
49.         \{  
50.             cin >> num;  
51.             a\[i\]\[j\] = num;  
52.         \}  
53.     \}  
54.   
55.     cout << MaxRecSum(n) << endl;  
56.     return 0;  
57. \}

[view plain]: http://blog.csdn.net/f_x_q/article/details/9616095#