18.12 Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.
这道求和最大的子矩阵，跟LeetCode上的Maximum Size Subarray Sum Equals k和Maximum Subarray很类似。这道题不建议使用brute force的方法，因为实在是不高效，我们需要借鉴上面LeetCode中的建立累计和矩阵的思路，我们先来看这道题的第一种解法，由于建立好累计和矩阵，那么我们通过给定了矩阵的左上和右下两个顶点的坐标可以在O(1)的时间内快速的求出矩阵和，所以我们要做的就是遍历矩阵中所有的子矩阵，然后比较其矩阵和，返回最大的即可，时间复杂度为O(n4)。
解法一：
vector<vector<int>> precompute(vector<vector<int>> &matrix) { vector<vector<int>> sumMatrix = matrix; for (int i = 0; i < matrix.size(); ++i) { for (int j = 0; j < matrix[i].size(); ++j) { if (i == 0 && j == 0) { sumMatrix[i][j] = matrix[i][j]; } else if (j == 0) { sumMatrix[i][j] = sumMatrix[i - 1][j] + matrix[i][j]; } else if (i == 0) { sumMatrix[i][j] = sumMatrix[i][j - 1] + matrix[i][j]; } else { sumMatrix[i][j] = sumMatrix[i - 1][j] + sumMatrix[i][j - 1] - sumMatrix[i - 1][j - 1] + matrix[i][j]; } } } return sumMatrix; } int compute_sum(vector<vector<int>> &sumMatrix, int i1, int i2, int j1, int j2) { if (i1 == 0 && j1 == 0) { return sumMatrix[i2][j2]; } else if (i1 == 0) { return sumMatrix[i2][j2] - sumMatrix[i2][j1 - 1]; } else if (j1 == 0) { return sumMatrix[i2][j2] - sumMatrix[i1 - 1][j2]; } else { return sumMatrix[i2][j2] - sumMatrix[i2][j1 - 1] - sumMatrix[i1 - 1][j2] + sumMatrix[i1 - 1][j1 - 1]; } } int get_max_matrix(vector<vector<int>> &matrix) { int res = INT_MIN; vector<vector<int>> sumMatrix = precompute(matrix); for (int r1 = 0; r1 < matrix.size(); ++r1) { for (int r2 = r1; r2 < matrix.size(); ++r2) { for (int c1 = 0; c1 < matrix[0].size(); ++c1) { for (int c2 = c1; c2 < matrix[0].size(); ++c2) { int sum = compute_sum(sumMatrix, r1, r2, c1, c2); res = max(res, sum); } } } } return res; }
其实这道题的解法还能进一步优化到O(n3)，根据LeetCode中的那道Maximum Subarray的解法，我们可以对一维数组求最大子数组的时间复杂度优化到O(n)，那么我们可以借鉴其的思路，由于二维数组中遍历所有的列数相等的子矩阵的时间为O(n2)，每一行的遍历是O(n)，所以整个下来的时间复杂度即为O(n3)，参见代码如下：
解法二：
int max_subarray(vector<int> &array) { int res = 0, sum = 0; for (int i = 0; i < array.size(); ++i) { sum += array[i]; res = max(res, sum); sum = max(sum, 0); } return res; } int max_submatrix(vector<vector<int>> &matrix) { if (matrix.empty() || matrix[0].empty()) return 0; int res = 0; for (int r1 = 0; r1 < matrix.size(); ++r1) { vector<int> sum(matrix[0].size()); for (int r2 = r1; r2 < matrix.size(); ++r2) { for (int c = 0; c < matrix[0].size(); ++c) { sum[c] += matrix[r2][c]; } int t = max_subarray(sum); res = max(res, t); } } return res; }
本文转自博客园Grandyang的博客，原文链接：和最大的子矩阵[CareerCup] 18.12 Largest Sum Submatrix ，如需转载请自行联系原博主。
