[数据结构与算法]子矩阵最大和问题-动态规划

有个经典的动态规划题目，就是求连续子数组的最大和，那是一维的情况，如果推广到二维呢？这就产生了另一个经典的动态规划题目——子矩阵最大和，就是输入一个m*n的矩阵，找出在矩阵中，所有元素加起来之和最大的子矩阵。

例如在????0 -2 -7 0　这样一个4*4的矩阵中，元素之和最大的子矩阵为??9 2，它们之和为15。　

　　　　9? 2 -6 2　　　　　　　　　　　　　　　　　　　　　　　-4 1
　　　? -4 1 -4 1　　　　　　　　　　　　　　　　　　　　　　　 -1 8
　　　? -1 8 0 -2

这道题最直观的思路当然是暴力解法，但需要遍历所有的子数组求和，时间复杂度，想到一维的情况，时间复杂度是O(n)，是否能用类似的思路降低二维情况的时间复杂度，答案是肯定的。

一个m×n的矩阵matrix的子矩阵行数j满足1 ≤ j ≤ m，考虑第0到第j-1行的子矩阵，最多有n列，我们不考虑子矩阵的列数，先分别将每列的第0~j-1行的元素求和，这样就得到了一个长度为n的数组，是不是就可以按照一维的情况进行动态规划了？最终得到的结果就是元素(0, 0)到元素(j - 1, n)这个范围内所有行数为j的子矩阵的最大和。以此类推，可以对所有可能的行数的子矩阵分别求出最大和，再取出其中最大的就是题目需要的结果。

对于行数j的子矩阵，不考虑列数，可能的组合有m-j+1种，因此整个[1, m]区间总的组合数是m(m+1)/2，再考虑对每个长度为n的数组做动态规划，最终的时间复杂度是。类似的，也可以按列进行动态规划，此时的时间复杂度为。所以，m小就按行来，n小就按列来。

另外，可以先用一个矩阵sumMtr保存每列的行累计和，sumMtr[i][j]表示sum(matrix[0][j],?matrix[1][j], ..., [i-1][j])，这样求矩阵第matrix[i][k]到第matrix[j][k]个元素的和，直接通过sumMtx[j][k] - sumMtx[i - 1][k]（如果i==0，则直接取sum[j][k]）就能得到，就无须在遍历中重新求一次和。

?好，下面是你们喜欢代码环节。

public class MatrixQuery {

	public int maxSubmatrixSum(int[][] matrix) {
		int nrow = matrix.length, ncol = matrix[0].length;
		int[][] sumMtx = new int[nrow][ncol];
		for (int i = 0; i < nrow; ++i) {
			for (int j = 0; j < ncol; ++j) {
				sumMtx[i][j] = i == 0 ? matrix[i][j] : matrix[i][j] + sumMtx[i - 1][j];
			}
		}

		int maxSum = matrix[0][0];
		for (int i = 0; i < nrow; ++i) {
			for (int j = 0; j < nrow; ++j) {
				int tmpSum = 0;
				for (int k = 0; k < ncol; ++k) {
					int ele = i == 0 ? sumMtx[j][k] : sumMtx[j][k] - sumMtx[i - 1][k];
					tmpSum = Math.max(tmpSum + ele, ele);
					maxSum = Math.max(maxSum, tmpSum);
				}
			}
		}

		return maxSum;
	}

	public static void main(String[] args) {
		MatrixQuery mq = new MatrixQuery();
		int[][] mtx1 = { { 9, 2, -6, 2 }, { -4, 1, -4, 1 }, { -1, 8, 0, -2 } };
		System.out.println(mq.maxSubmatrixSum(mtx1));

		int[][] mtx2 = { { -4, 1 }, { -1, 8 } };
		System.out.println(mq.maxSubmatrixSum(mtx2));

		int[][] mtx3 = { { 1, 2 }, { 3, 4 } };
		System.out.println(mq.maxSubmatrixSum(mtx3));
	}
}

输出结果

15
9
10