Max Sum of Rectangle No Larger Than K

Given a non-empty 2D matrixmatrixand an integerk, find the max sum of a rectangle in thematrixsuch that its sum is no larger thank.

Example:

Given matrix = [
  [1,  0, 1],
  [0, -2, 3]
]
k = 2

The answer is2. 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 #1:

Modified brute force. Iterate through all possible rectangles by get subarray sums for all columns, and then find max subarray sum <= k for each column array; or columns first and then rows.

public int maxSumSubmatrix(int[][] matrix, int k) {
    if (matrix == null || matrix.length == 0 ||
        matrix[0] == null || matrix[0].length == 0) {
            return Integer.MIN_VALUE;
    }
    int row = matrix.length;
    int col = matrix[0].length;
    int max = Integer.MIN_VALUE;
    //start col range
    for (int startCol = 0; startCol < col; startCol++) {
        int[] dp = new int[row];
        //col index
        for (int i = startCol; i < col; i++) {
            //row index
            for (int j = 0; j < row; j++) {
                dp[j] += matrix[j][i];
            }
            max = Math.max(getMaxSubarraySum(dp, k), max);
        }
    }
    return max;
}
public int getMaxSubarraySum(int[] nums, int k) {
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = nums[i];
        if (nums[i] <= k) {
            max = Math.max(max, nums[i]);
        }
        for (int j = i + 1; j < nums.length; j++) {
            sum += nums[j];
            if (sum <= k) {
                max = Math.max(max, sum);
            }
        }
    }
    return max;
}

Solution #2:

Use TreeSet to optimize the getMaxSubarraySum function from n^2 to log(n).

public int getMaxSubarraySum(int[] nums, int k) {
    TreeSet<Integer> tSet = new TreeSet<>();
    tSet.add(0);
    int sum = 0,
        max = Integer.MIN_VALUE;
    for (int num : nums) {
        sum += num;
        Integer res = tSet.ceiling(sum - k);
        if (res != null) {
            max = Math.max(max, sum - res);
        }
        tSet.add(sum);
    }
    return max;
}