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;
} |