程序员面试金典 – 面试题 17.24. 最大子矩阵（转成一维最大子序和 DP）网络Michael是个半路程序员-

1. 题目

给定一个正整数和负整数组成的 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 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-submatrix-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 前缀和（超时）

• 求出每个位置与(0,0)构成的子矩阵的和
• 4层 for 循环遍历左上角为（x,y），右下角为（i，j）的子矩阵
• 其和为
  $sum = prefixsum[i][j]-prefixsum[x-1][j]-prefixsum[i][y-1]+prefixsum[x-1][y-1]$

  sum=prefixsum[i][j]−prefixsum[x−1][j]−prefixsum[i][y−1]+prefixsum[x−1][y−1]

• 复杂度
  $O(m^2n^2)$

  O(m2n2)，通过14/25个测试

class Solution { public:     vector<int> getMaxMatrix(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(), i, j, x, y; int sum, maxSum = INT_MIN;      vector<vector<int>> prefixsum(matrix); for(i = 0; i < m; ++i) { for(j = 0; j < n; ++j) { if(i > 0)         prefixsum[i][j] += prefixsum[i-1][j]; if(j > 0)         prefixsum[i][j] += prefixsum[i][j-1]; if(i>0 && j>0)         prefixsum[i][j] -= prefixsum[i-1][j-1]; // cout << prefixsum[i][j] << " "; } // cout << endl; }      vector<int> ans(4); for(i = 0; i < m; i++) { for(j = 0; j < n; ++j) { for(x = 0; x <= i; x++) { for(y = 0; y <= j; y++) {          sum = prefixsum[i][j]; if(x > 0)           sum -= prefixsum[x-1][j]; if(y > 0)           sum -= prefixsum[i][y-1]; if(x > 0 && y > 0)           sum += prefixsum[x-1][y-1]; if(sum > maxSum) {           maxSum = sum;           ans[0] = x, ans[1] = y;           ans[2] = i, ans[3] = j; } } } } } return ans; } }; 

2.2 动态规划

类似题目：
LeetCode 152. 乘积最大子序列（DP）
本题参考：LeetCode 53. 最大子序和（动态规划），本质一样。

• 2层for循环先把所有可能的行组合找出来
• 然后列向求和，压扁它
• 对这个压扁的一维数组求最大子序和即可
• 时间复杂度
  $O(m^2n)$

  O(m2n)

class Solution { public:     vector<int> getMaxMatrix(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(), i, j, k, l, r; int sum, maxSum = INT_MIN;      vector<int> sumRi_Rj(n);//【i，j】行的列向和      vector<int> ans(4); for(i = 0; i < m; ++i) {       sumRi_Rj.clear();       sumRi_Rj.resize(n,0); for(j = i; j < m; ++j) { for(k = 0; k < n; ++k) {         sumRi_Rj[k] += matrix[j][k];//列向和 } //一维dp，初始化        sum = sumRi_Rj[0];        l = r = 0; if(sum > maxSum) {                     maxSum = sum;                     ans[0] = i, ans[1] = l;                     ans[2] = j, ans[3] = r; } for(k = 1; k < n; ++k) { //转为一维数组sumRi_Rj最大子数组和 if(sum > 0) {          sum += sumRi_Rj[k];          r = k; } else {          sum = sumRi_Rj[k];          l = r = k; } if(sum > maxSum) {          maxSum = sum;          ans[0] = i, ans[1] = l;          ans[2] = j, ans[3] = r; } } } } return ans; } }; 

384 ms 12.7 MB