1 /* 2 本程序说明： 3  4 给定一个矩阵matrix,其中有正有负有0，返回子矩阵的最大累加和 5 例如矩阵matrix为： 6 -90 48 78 7 64 -40 64 8 -81 -7 66 9 其中最大累加和的子矩阵为10 48 7811 -40 6412 -7 6613 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 }