[CareerCup] 18.12 Largest Sum Submatrix 和最大的子矩阵 - Grandyang - 博客园

[CareerCup] 18.12 Largest Sum Submatrix 和最大的子矩阵 - Grandyang - 博客园
18.12 Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.
 https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2017.%20Hard/Q17_24_Max_Submatrix
这道求和最大的子矩阵，跟LeetCode上的Maximum Size Subarray Sum Equals k和Maximum Subarray很类似。

If we have R rows and C columns, we can solve it in O(R^2C) time.
public class SubMatrix {
private int row1, row2, col1, col2, sum;
}
public class Range {
public int start, end, sum;
}

public static SubMatrix getMaxMatrix(int[][] matrix) {
int rowCount = matrix.length;
int colCount = matrix[0].length;

SubMatrix best = null;

for (int rowStart = 0; rowStart < rowCount; rowStart++) {
int[] partialSum = new int[colCount];

for (int rowEnd = rowStart; rowEnd < rowCount; rowEnd++) {
/* Add values at row rowEnd. */
for (int i = 0; i < colCount; i++) {
partialSum[i] += matrix[rowEnd][i];
}

Range bestRange = maxSubArray(partialSum, colCount);
if (best == null || best.getSum() < bestRange.sum) {
best = new SubMatrix(rowStart, bestRange.start, rowEnd, bestRange.end, bestRange.sum);
}
}
}
return best;
}

public static Range maxSubArray(int[] array, int N) {
Range best = null;
int start = 0;
int sum = 0;

for (int i = 0; i < N; i++) {
sum += array[i];
if (best == null || sum > best.sum) {
best = new Range(start, i, sum);
}

/* If running_sum is < 0 no point in trying to continue the
* series. Reset. */
if (sum < 0) {
start = i + 1;
sum = 0;
}
}
return best;
}

这道题不建议使用brute force的方法，因为实在是不高效，我们需要借鉴上面LeetCode中的建立累计和矩阵的思路，我们先来看这道题的第一种解法，由于建立好累计和矩阵，那么我们通过给定了矩阵的左上和右下两个顶点的坐标可以在O(1)的时间内快速的求出矩阵和，所以我们要做的就是遍历矩阵中所有的子矩阵，然后比较其矩阵和，返回最大的即可，时间复杂度为O(n⁴)。
public static SubMatrix getMaxMatrix(int[][] matrix) {
SubMatrix best = null;
int rowCount = matrix.length;
int columnCount = matrix[0].length;
int[][] sumThrough = precomputeSums(matrix);

for (int row1 = 0; row1 < rowCount; row1++) {
for (int row2 = row1; row2 < rowCount; row2++) {
for (int col1 = 0; col1 < columnCount; col1++) {
for (int col2 = col1; col2 < columnCount; col2++) {
int sum = sum(sumThrough, row1, col1, row2, col2);
if (best == null || best.getSum() < sum) {
best = new SubMatrix(row1, col1, row2, col2, sum);
}
}
}
}
}
return best;
}

private static int[][] precomputeSums(int[][] matrix) {
int[][] sumThrough = new int[matrix.length][matrix[0].length];
for (int r = 0; r < matrix.length; r++) {
for (int c = 0; c < matrix[0].length; c++) {
int left = c > 0 ? sumThrough[r][c - 1] : 0;
int top = r > 0 ? sumThrough[r - 1][c] : 0;
int overlap = r > 0 && c > 0 ? sumThrough[r - 1][c - 1] : 0;
sumThrough[r][c] = left + top - overlap + matrix[r][c];
}
}
return sumThrough;
}

private static int sum(int[][] sumThrough, int r1, int c1, int r2, int c2) {
int topAndLeft = r1 > 0 && c1 > 0 ? sumThrough[r1 - 1][c1 - 1] : 0;
int left = c1 > 0 ? sumThrough[r2][c1 - 1] : 0;
int top = r1 > 0 ? sumThrough[r1 - 1][c2] : 0;
int full = sumThrough[r2][c2];
return full - left - top + topAndLeft;
}

O(N^6)
public static SubMatrix getMaxMatrix(int[][] matrix) {
int rowCount = matrix.length;
int columnCount = matrix[0].length;
SubMatrix best = null;
for (int row1 = 0; row1 < rowCount; row1++) {
for (int row2 = row1; row2 < rowCount; row2++) {
for (int col1 = 0; col1 < columnCount; col1++) {
for (int col2 = col1; col2 < columnCount; col2++) {
int sum = sum(matrix, row1, col1, row2, col2);
if (best == null || best.getSum() < sum) {
best = new SubMatrix(row1, col1, row2, col2, sum);
}
}
}
}
}
return best;
}

private static int sum(int[][] matrix, int row1, int col1, int row2, int col2) {
int sum = 0;
for (int r = row1; r <= row2; r++) {
for (int c = col1; c <= col2; c++) {
sum += matrix[r][c];
}
}
return sum;
}

Read full article from [CareerCup] 18.12 Largest Sum Submatrix 和最大的子矩阵 - Grandyang - 博客园