363. Max Sum of Rectangle No Larger Than K

题目链接：

参考discussion里的解释：

先是如何在2d矩阵里找max sum的问题，参考视频：

然后就是一个array里面找不大于k的最大值问题了:

要找到最大的sum <= k, 用cumulative sum就是cum[j] - k <= cum[i]，upper_bound就是TreeSet来做了。

public class Solution {    public int maxSumSubmatrix(int[][] matrix, int k) {        if(matrix.length == 0 || matrix.length == 0) return 0;                int m = matrix.length, n = matrix[0].length;        int global = Integer.MIN_VALUE;        // m >> n        for(int j = 0; j < n; j++) {            int[] col = new int[m];            for(int p = j; p < n; p++) {                // cumulative sum                for(int i = 0; i < m; i++) col[i] += matrix[i][p];                // maximum array sum < k                TreeSet
    
      set = new TreeSet();                // include 1 line                set.add(0);                int prefixSum = 0, local = Integer.MIN_VALUE;                for(int sum : col) {                    prefixSum += sum;                    // upper_bound                    Integer cum = set.ceiling(prefixSum - k);                    if(cum != null) local = Math.max(local, prefixSum - cum);                    set.add(prefixSum);                }                global = Math.max(global, local);            }        }                return global;    }}
    

另外找最大不超过k的range sum还可以用merge sort，参考discussion：