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:

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?

class Solution {
    private int maxSumSubArray(int[] arr, int k) {
        int max = Integer.MIN_VALUE;
        int currSum = 0;
        TreeSet<Integer> set = new TreeSet();
        set.add(0);
        for (int i = 0; i < arr.length; i++) {
            currSum += arr[i];
            Integer gap = set.ceiling(currSum - k);
            if (gap != null)
                max = Math.max(max, currSum - gap);
            set.add(currSum);
        }
        return max;
    }

    public int maxSumSubmatrix(int[][] matrix, int target) {
        if (matrix.length == 0)
            return 0;
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < matrix[0].length; i++) {
            int[] sum = new int[matrix.length];
            for (int j = i; j < matrix[0].length; j++) {
                for (int k = 0; k < matrix.length; k++)
                    sum[k] += matrix[k][j];
                int bestSum = maxSumSubArray(sum, target);
                ans = Math.max(ans, bestSum);
                if (ans == target)
                    return ans;
            }
        }
        return ans;
    }
}