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

糖逗

题目描述：

给定一个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

注意：本题相对书上原题稍作改动

示例:

输入:
[
   [-1,0],
   [0,-1]
]
输出: [0,1,0,1]
解释: 输入中标粗的元素即为输出所表示的矩阵
说明：

1 <= matrix.length, matrix[0].length <= 200

    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        int pos1 = 0, pos2 = 0, pos3 = 0, pos4 = 0, globalmax = INT_MIN;
        int row = matrix.size(), col = matrix[0].size();
        int max_ = INT_MIN;
        for(int i = 0; i < row; i++){
            vector<int> temp(col, 0);
            for(int j = i; j < row; j++){
                int curmax = INT_MIN, temp1 = 0;
                for(int k = 0; k < col; k++){
                    temp[k] += matrix[j][k];
                    if(curmax <= 0){
                        temp1 = k;
                        curmax = temp[k];
                    }
                    else{
                        curmax += temp[k];
                    }
                    if(curmax > globalmax){
                        globalmax = curmax;
                        pos1 = i;
                        pos2 = temp1;
                        pos3 = j;
                        pos4 = k;

                    }
                }
            }
        }
        return {pos1, pos2, pos3, pos4};
    }

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