[itint5]最大子矩阵和

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

  

[itint5]最大子矩阵和

上一篇:HIVE中内连接和左半连接不一致问题


下一篇:微信浏览器中调用支付宝支付