Max Sum of Rectangle No Larger Than K

Question

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:

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

Analysis

First, we can deduce this matrix 2D problem into a 1D problem. Suppose there is an array with n numbers, how can we find the subarray with max sum no larger than K?

Similar to this subproblem, the Problem of finding the max sum without upper bound can be solved in linear Time complexity using Dynamic Programming approach. With upper bound restriction, we have to find the subarray that sums up no larger than k. To do this, we can use another array sum[] where sum[i] record the sum of subarray [0,i], we add all the previous subarray sum to a TreeSet from which we can find the largest potential subsum. Then inall, we can find the max sum with upper bound restruction in O(nlogn) time.

Secondly, apply this 1D problem to 2 Dimension. We can treat each column as a 1 Dimension Array, and appending successive columns covers the rectrangle cases.

Solution:

public int maxSumSubmatrix(int[][] matrix, int k) {
        int row=matrix.length, col=matrix[0].length;
        if(row==0 || col==0) return Integer.MIN_VALUE;
        int result=Integer.MIN_VALUE;
        for(int left=0;left<col;left++){
            int[] tmp=new int[row];
            for(int right=left;right<col;right++){
                for(int i=0;i<row;i++) tmp[i]+=matrix[i][right];
                TreeSet<Integer> set=new TreeSet<>();
                set.add(0);
                int sum=0;
                for(int n : tmp){
                    sum+=n;
                    Integer num=set.ceiling(sum-k);
                    if(num!=null) result=Math.max(result,sum-num);
                    set.add(sum);
                }
            }
        }
        return result;
    }