363. Max Sum of Rectangle No Larger Than K

Link

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:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2 
Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2,
             and 2 is the max number no larger than k (k = 2).

Note:

1. The rectangle inside the matrix must have an area > 0.

2. What if the number of rows is much larger than the number of columns?

Solution

先固定Col的range，假設從R到L

取得R-L區間的sums

然後對每組R-L的sums array的內容計算是否有個區間滿足<=K，如何找到區間的方法是將sums值內容從頭到尾進行加總(currentSum)，並存於treeMap之中。

並尋找treeMap中是否已經有一組之前的previousSum 大於等於currentSum-k 那麼current到previous之間的區間 sum值就會是 curentSum - previousSum 且會<= k。

T: O(col*col*(row+rowlogrow)) = O(col^2*rowlogrow)

T: O(row)

 public int maxSumSubmatrix(int[][] matrix, int k) {
        int max = Integer.MIN_VALUE;
        int[] sums = new int[matrix.length];
        for(int l = 0; l < matrix[0].length; l++){
            Arrays.fill(sums, 0);
            //計算R-L 的sums 
            for(int r = l; r < matrix[0].length; r++){
                for(int i = 0; i < sums.length; i++){
                    sums[i] += matrix[i][r];
                }
                //we use TreeSet to help us find the rectangle with maxSum <= k with                        O(logN) time
                TreeSet<Integer> set = new TreeSet<Integer>();
                //add 0 to cover the single row case
                set.add(0);
                int currSum = 0;
            
                for(int sum : sums){
                    currSum += sum;
                    //we use sum subtraction (curSum - sum) to get the subarray with sum <= k
                    //therefore we need to look for the smallest sum >= currSum - k
                    Integer num = set.ceiling(currSum - k);
                    if(num != null) max = Math.max( max, currSum - num );
                    set.add(currSum);
                }
            }
        }
        return max;
    }