代码:
1 /*
2 本程序说明:
3
4 给定一个矩阵matrix,其中有正有负有0,返回子矩阵的最大累加和
5 例如矩阵matrix为:
6 -90 48 78
7 64 -40 64
8 -81 -7 66
9 其中最大累加和的子矩阵为
10 48 78
11 -40 64
12 -7 66
13
14 */
15 #include <iostream>
16 #include <vector>
17 using namespace std;
18
19 int SubMatrixMaxSum(const vector<vector<int> >& matrix)
20 {
21 int max_sum=0;
22 for(size_t i=0;i<matrix.size();++i)
23 {
24 vector<int> s(matrix[0].size());
25 for(size_t j=i;j<matrix[0].size();++j)
26 {
27 int sum_cur=0;
28 for(size_t k=0;k<matrix[0].size();++k)
29 {
30 s[k]+=matrix[j][k];
31 sum_cur+=s[k];
32 sum_cur=sum_cur<0 ? 0 : sum_cur;
33 max_sum=max(max_sum,sum_cur);
34 }
35 }
36 }
37 return max_sum;
38 }
39
40 int main()
41 {
42 vector<vector<int> > matrix{{-90,48,78},{64,-40,64},{-81,-7,66}};43 cout<<SubMatrixMaxSum(matrix)<<endl;
44 return 0;
45 }