C++刷leetcode（面试题 17.24. 最大子矩阵）【动态规划转化成最大子序列和问题】

糖逗

题目描述：

1. 
   
2. 给定一个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
   
3. 
   
4. 返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
   
5. 
   
6. 注意：本题相对书上原题稍作改动
   
7. 
   
8. 示例:
   
9. 
   
10. 输入:
    
11. [
    
12.    [-1,0],
    
13.    [0,-1]
    
14. ]
    
15. 输出: [0,1,0,1]
    
16. 解释: 输入中标粗的元素即为输出所表示的矩阵
    
17. 说明：
    
18. 
    
19. 1 <= matrix.length, matrix[0].length <= 200

复制代码

1.     vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
   
2.         int pos1 = 0, pos2 = 0, pos3 = 0, pos4 = 0, globalmax = INT_MIN;
   
3.         int row = matrix.size(), col = matrix[0].size();
   
4.         int max_ = INT_MIN;
   
5.         for(int i = 0; i < row; i++){
   
6.             vector<int> temp(col, 0);
   
7.             for(int j = i; j < row; j++){
   
8.                 int curmax = INT_MIN, temp1 = 0;
   
9.                 for(int k = 0; k < col; k++){
   
10.                     temp[k] += matrix[j][k];
    
11.                     if(curmax <= 0){
    
12.                         temp1 = k;
    
13.                         curmax = temp[k];
    
14.                     }
    
15.                     else{
    
16.                         curmax += temp[k];
    
17.                     }
    
18.                     if(curmax > globalmax){
    
19.                         globalmax = curmax;
    
20.                         pos1 = i;
    
21.                         pos2 = temp1;
    
22.                         pos3 = j;
    
23.                         pos4 = k;
    
24. 
    
25.                     }
    
26.                 }
    
27.             }
    
28.         }
    
29.         return {pos1, pos2, pos3, pos4};
    
30.     }

复制代码

参考链接：https://leetcode-cn.com/problems ... o-qi-you-jian-dao-/