Max Sum of Rectangle No Larger Than K

LeetCode Q 363 - Max Sum of Rectangle No Larger Than K

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:

• The rectangle inside the matrix must have an area > 0.
• What if the number of rows is much larger than the number of columns?

Solution

Code:

public int maxSumSubmatrix(int[][] matrix, int k) {

  if (matrix.length == 0 || matrix[0].length == 0) return 0;

  int R = matrix.length, C = matrix[0].length;

  int res = Integer.MIN_VALUE;

  for (int c1 = 0; c1 < C; c1++) {
    for (int c2 = c1; c2 < C; c2++) {

      int[] area = new int[R];
      for (int r = 0; r < R; r++) {
        for (int c = c1; c <= c2; c++) {
          area[r] += matrix[r][c];
        }
      }

      TreeSet<Integer> set = new TreeSet<>();
      set.add(0);
      int sum = 0;

      for (int r = 0; r < R; r++) {
        sum += area[r];
        Integer ceiling = set.ceiling(sum - k);

        if (Integer != null) 
          res = Math.max(res, sum - ceiling);

          set.add(sum);
      }
    }
  }

  return res;
}