最大子矩阵

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

题解

最大子矩阵，可以先转化为求一行的最大字序列和，通过把这个问题升到二维解决。本题是一个DP问题。

其实具体算法在算法书上已经有了，只不过书上的例题在均为负数时，最大值为0。而这道题如果均为负数，还要输出最大的负数，所以只要做一个小改动就好了，我写了一个算法，同时LeetCode上面还有一个更好的算法，在这里简单讲解一下。

先看我写的（嘿嘿）

#include <iostream>
#include <vector>
using namespace std;

#define r 2
#define l 2
class Solution {
 public:
  int maxSubArray(vector<int>& nums, int& c1, int& c2) {
    int b = 0, sum = INT_MIN,c1_temp;
    for (int i = 0; i < nums.size(); i++) {
      if (b > 0) {
        b += nums[i];
      } else {
        b = nums[i];
        c1_temp = i;
      }
      if (b > sum ) {
        sum = b;
        c2 = i;
        c1=c1_temp;
      }
    }
    return sum;
  }
  vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
    int max, c1, c2, r1, r2, Max_final = INT_MIN, c1_final, c2_final;
    r1 = r2 = c1_final = c2_final =c1=c2= 0;
    vector<int> ans(4);
    for (int i = 0; i < matrix.size(); i++) {
      vector<int> li(matrix[0].size());  //默认值为0
      for (int j = i; j < matrix.size(); j++) {
        for (int k = 0; k < matrix[0].size(); k++) {
          li[k] += matrix[j][k];
        }
        max = maxSubArray(li, c1, c2);
        if (max > Max_final) {
          Max_final = max;
          r1 = i, r2 = j;
          c1_final = c1, c2_final = c2;
        }
      }
    }
    ans[0] = r1;
    ans[1] = c1_final;
    ans[2] = r2;
    ans[3] = c2_final;
    return ans;
  }
};

int main() {
  int array[r][l] = {-1, 0,0,-1};
  vector<vector<int>> matrix(r, vector<int>(l));
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < l; j++) {
      matrix[i][j] = array[i][j];
    }
  }
  Solution s;
  s.getMaxMatrix(matrix);
}

因为自己测试了一下，实际上的算法只有class中的内容。

maxSubArray用来计算一行的字序列最大值，输出列的范围

getMaxMatrix通过调用maxSubArray，实现矩阵的计算。

这个方法稍微有点麻烦在于，其实maxSubArray可以写进getMaxMatrix里，就有了下面这个程序，核心思想都是一样的。

更新了算法的格式

这样写比上面的更简洁

/*
  1.动态规划，压缩成行矩阵
*/
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int m, n, MAX = 0, init_n, end_n;
  cin >> m >> n;
  vector<vector<int>> vec(m, vector<int>(n));
  vector<int> ans(4);
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      cin >> vec[i][j];
    }
  }
  for (int i = 0; i < m; i++) {
    vector<int> dp(n);
    for (int j = i; j < m; j++) {
      int sum = 0, b = 0;
      for (int k = 0; k < n; k++) {
        dp[k] += vec[j][k];
        if (b > 0) {
          b += dp[k];
        } else {
          b = dp[k];
          init_n = k;
        }
        if (b > sum) {
          sum = b;
          end_n = k;
        }
      }
      if (sum > MAX) {
        MAX = sum;
        ans[0] = i;
        ans[1] = j;
        ans[2] = init_n;
        ans[3] = end_n;
      }
    }
  }
  cout << MAX<<endl;
  cout<<ans[0]+1;
  for(int i=1;i<4;i++){
    cout<<' '<<ans[i]+1;
  }
  system("pause");
}

每次移动k时计算当前列的最大序列，加完一行直接计算完成，减小了时间复杂度，也增加了程序的可读性。

就到这里，有兴趣的可以再去实现一下。

---