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).

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?

Credits:

Special thanks to for adding this problem and creating all test cases.

Analysis:

Take the following analysis from https://discuss.leetcode.com/topic/48854/java-binary-search-solution-time-complexity-min-m-n-2-max-m-n-log-max-m-n

 

/* first  consider the situation matrix is 1D    we can save every sum of 0~i(0<=i

1 public class Solution { 2     public int maxSumSubmatrix(int[][] matrix, int k) { 3         if (matrix.length == 0 || matrix[0].length == 0) 4             return Integer.MIN_VALUE; 5  6         int res = Integer.MIN_VALUE; 7         int row = matrix.length; 8         int col = matrix[0].length; 9         int m = Math.min(row, col);10         int n = Math.max(row, col);11         boolean moreCol = (col > row);12 13         for (int i = 0; i < m; i++) {14             int[] sum = new int[n];15             for (int j = i; j >= 0; j--) {16                 int val = 0;17                 TreeSet
     
       sumSet = new TreeSet
      
       ();18                 sumSet.add(0);19                 for (int l = 0; l < n; l++) {20                     sum[l] = sum[l] + ((moreCol) ? matrix[j][l] : matrix[l][j]);21                     val += sum[l];22                     Integer other = sumSet.ceiling(val - k);23                     if (other != null) {24                         res = Math.max(res, val - other);25                     }26                     sumSet.add(val);27                 }28             }29         }30 31         return res;32     }33 }