最大子矩阵动态规划代码

这是一个求解最大子矩阵的动态规划代码。该算法的时间复杂度为O(n^3)，其中n为矩阵的行数或列数。具体实现过程如下：

1. 遍历起始行r1，遍历结束行r2，将当前i~j行组成的矩阵的每一列的和存放在数组b中。

2. 对于每个矩阵，将其转化为一维数组，然后求解最大子序列和，并保存其左上角和右下角的坐标。

3. 不断记录较好的结果，最终返回最大子矩阵的左上角和右下角坐标。

下面是该算法的代码实现，其中matrix为输入的二维矩阵，返回一个长度为4的vector，分别表示最大子矩阵的左上角和右下角坐标。

class Solution {
public:
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        int rows=matrix.size(), cols=matrix[0].size();
        int maxMat=INT32_MIN;
        vector<int> ans(4, -1);
        for(int r1=0;r1<rows;++r1){//遍历起始行
            vector<int> nums(cols);//矩阵某两行间元素按列求和
            for(int r2=r1;r2<rows;++r2){//遍历结束行
                //最大字段和问题
                int dp=0, c1=-1;
                for(int c2=0;c2<cols;++c2){//遍历和数组，实际上是边遍历边完成求和
                    nums[c2]+=matrix[r2][c2];//将新的一行中第i个元素加到前面若干行在位置i的和
                    if(dp>0){//前面的字段有和为正，可以把前面一部分也带上
                        dp+=nums[c2];
                    }
                    else{//前面一段为负，拖后腿直接抛弃
                        dp=nums[c2];
                        c1=c2;
                    }
                    if(dp>maxMat){//不断记录较好的结果
                        maxMat=dp;
                        ans[0]=r1;
                        ans[1]=c1;                        ans[2]=r2;
                        ans[3]=c2;
                    }
                }
            }
        }
        return ans;
    }
};