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; }}新聞熱點
疑難解答
