首页 > 代码库 > 《Cracking the Coding Interview》——第18章：难题——题目12

《Cracking the Coding Interview》——第18章：难题——题目12

2024-07-02 00:23:25   225人阅读

2014-04-29 04:36

题目：最大子数组和的二位扩展：最大子矩阵和。

解法：一个维度上进行枚举，复杂度O(n^2)；另一个维度执行最大子数组和算法，复杂度O(n)。总体时间复杂度为O(n^3)，还需要O(n)额外空间。

代码：

 1 // 18.12 Given an n x n matrix, find the submatrix with largest sum. Return the sum as the result.
 2 #include <algorithm>
 3 #include <climits>
 4 #include <iostream>
 5 #include <vector>
 6 using namespace std;
 7 
 8 class Solution {
 9 public:
10     int largestSubmatrixSum (const vector<vector<int> > &matrix) {
11         n = matrix.size();
12         if (n == 0) {
13             return 0;
14         }
15         m = matrix[0].size();
16         if (m == 0) {
17             return 0;
18         }
19         
20         int i, j, k;
21         vector<int> v;
22         int msum;
23         int sum;
24         
25         v.resize(m);
26         msum = INT_MIN;
27         for (i = 0; i < n; ++i) {
28             fill(v.begin(), v.end(), 0);
29             for (j = i; j < n; ++j) {
30                 for (k = 0; k < m; ++k) {
31                     v[k] += matrix[j][k];
32                 }
33                 sum = maxSubarraySum(v, m);
34                 msum = max(msum, sum);
35             }
36         }
37         v.clear();
38         return msum;
39     };
40 private:
41     int n, m;
42     
43     int maxSubarraySum(const vector<int> &v, int n) {
44         int msum;
45         int sum;
46         int i;
47         
48         msum = INT_MIN;
49         for (i = 0; i < n; ++i) {
50             if (v[i] >= 0) {
51                 msum = max(msum, v[i]);
52                 break;
53             }
54         }
55         if (i == n) {
56             return msum;
57         }
58         
59         msum = sum = 0;
60         for (i = 0; i < n; ++i) {
61             sum += v[i];
62             msum = max(msum, sum);
63             sum = max(sum, 0);
64         }
65         
66         return msum;
67     };
68 };
69 
70 int main()
71 {
72     int i, j;
73     int n, m;
74     vector<vector<int> > matrix;
75     Solution sol;
76     
77     while (cin >> n >> m && (n > 0 && m > 0)) {
78         matrix.resize(n);
79         for (i = 0; i < n; ++i) {
80             matrix[i].resize(m);
81             for (j = 0; j < m; ++j) {
82                 cin >> matrix[i][j];
83             }
84         }
85         cout << sol.largestSubmatrixSum(matrix) << endl;
86         
87         for (i = 0; i < n; ++i) {
88             matrix[i].clear();
89         }
90         matrix.clear();
91     }
92     
93     return 0;
94 }

 


联系
我们