Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k. Example: Given matrix = [ [1, 0, 1], [0, -2, 3] ] k = 2 The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2).
这道题目其实是两个子问题的结合，解决了这两个子问题可以很容易的解决此题。
也就是在一个二维数组中，寻找一个最大直方和。暴力解法就是取矩形对角两点的元素，进行遍历求和，复杂度是O(MNMN). 暴力循环可以通过动态规划进行优化，用一个数组存储当前矩形的累计和。如下图： 
绿色数组记录了蓝色区域的和，通过数组记录下之前的值避免了重复计算。在绿色数组中，寻找不大于k的最大和连续子数组，相当于在确定了蓝色矩形左右边界的情况下，通过修改上下边界寻找最大和矩形。同样，全遍历二维数组每一列：
。。。 
全遍历后，则找出了全部矩形。
如果不包含不大于k的限制，那么就是一个普通的dp问题。类似于leetcode上这道题目： stock问题。 对于不大k的，则是构建一个二插查找树BST，java中对应可以使用TreeMap。对于一个数组，子数组(i,j]的和可以通过sum[0,j] - sum[0,i]来求出。在遍历这个子数组的时候计算出当前的累加和 rightSum并加入到BST中，记leftSum为之前存储在BST中的数，因为要求 rightSum - leftSum <=k，则有leftSum >= rightSum - k，同时leftSum越小，求和值rightSum-leftSum越大。所以去BST中找大于等于 rightSum-k的最小数leftSum，并更新全局最优，即得结果。
最终代码如下：
public class Solution { public int maxSumSubmatrix(int[][] matrix, int k) { int row = matrix.length; int col = matrix[0].length; int res = Integer.MIN_VALUE; //子问题1，三个for循环全遍历。 for (int i = 0;i < col;i++) { int[] arr = new int[row]; for (int j = i;j < col;j++) { int rightSum = 0; TreeSet<Integer> sums = new TreeSet<>(); sums.add(0); for (int l = 0; l < row;l++) { arr[l] += matrix[l][j]; //子问题二，寻找leftSum。计算最大和连续子数组 rightSum += arr[l]; Integer leftSum = sums.ceiling(rightSum - k); if (leftSum!=null) res = Math.max(res, rightSum - leftSum); sums.add(rightSum); } } } return res; }}新闻热点
疑难解答
