http://www.itint5.com/oj/#39
最大子矩阵和，复杂度O(n^3)。利用了最大子段和的方法。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 |
int
maxRectSum(vector<vector<int> > &matrix) { int
n = matrix.size(); if
(n == 0) return
0; int
m = matrix[0].size(); if
(m == 0) return
0; int
max = 0; for
(int
i = 0; i < m; i++) { vector<int> vec(n); for
(int
j = i; j < m; j++) { for
(int
k = 0; k < n; k++) { vec[k] += matrix[k][j]; } // vec[k]: sum of row k, from i to j int
sum = 0; for
(int
k = 0; k < n; k++) { if
(sum < 0) sum = 0; sum += vec[k]; if
(sum > max) max = sum; } } } return
max;} |
原文：http://www.cnblogs.com/lautsie/p/3529531.html