LeetCode [363] Max Sum of Rectangle No Larger Than K

 363. Max Sum of Rectangle No Larger Than K

Hard

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?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { public int maxSumSubmatrix(int[][] matrix, int k) { int m = matrix.length; if(m == 0) return 0; int n = matrix[0].length; if(n==0) return 0; int ret = Integer.MIN_VALUE; for(int i=0; i<n; ++i){ int sum[] = new int[m]; for(int j=i; j<n; ++j){ for(int t=0; t<m; ++t){ sum[t] += matrix[t][j]; } TreeSet<Integer> set = new TreeSet<>(); set.add(0); int s = 0; for(int x:sum){ s += x; Integer prv = set.ceiling(s-k); if(prv!=null){ ret = Math.max(ret, s-prv); } set.add(s); } } } return ret; } }