链接：

面试题 17.24. 最大子矩阵

题解：

这样我们就将二维问题转化为了一维问题，现在另一个问题就是怎么把所有情况都遍历到呢？

我们以第i行为第一行，向下延申，设最后一行为第j行，我们就i在这么一个范围内，将二维问题转化为一维问题，再求解最大子序列和

作者：bugsmaker
链接：https://leetcode.cn/problems/max-submatrix-lcci/solutions/137568/zhe-yao-cong-zui-da-zi-xu-he-shuo-qi-you-jian-dao-/

class Solution {
public:vector<int> getMaxMatrix(vector<vector<int>>& matrix) {int m = matrix.size();if (m <= 0) {return {};}int n = matrix[0].size();if (n <= 0) {return {};}std::vector<int> result(4);std::vector<std::vector<int>> prefix_sum(m+1, std::vector<int>(n+1, 0));// prefix[i][j] 表示以(i-1, j-1) 为右下角顶点的，(0, 0)左上角顶点矩阵的和for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {prefix_sum[i][j] = matrix[i-1][j-1] + prefix_sum[i][j-1] + prefix_sum[i-1][j] - prefix_sum[i-1][j-1]; }}int global_max = INT_MIN;// 枚举上边界for (int top = 0; top < m; ++top) {// 枚举下边界for (int bottom = top; bottom < m; ++bottom) {int local_max = 0;int left = 0;// 枚举最右边的列，获得窗口for (int right = 0; right < n; ++right) {// 获得当前窗口的的数值local_max = prefix_sum[bottom+1][right+1] - prefix_sum[bottom+1][left] -prefix_sum[top][right+1] + prefix_sum[top][left];// 如果比最大值大，则更新最大值，保存结果if (local_max > global_max) {global_max = local_max;result[0] = top;result[1] = left;result[2] = bottom;result[3] = right;}// 如果当前窗口已经变为负数，则更新窗口的左端点if (local_max < 0) {local_max = 0;left = right + 1;}}}            }return result;}
};