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:

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?

This problem utilizes an algorithm called Kadane's algorithm. To understand it using the link provided is quite an effort. Briefly speaking, it first fixes the left bound and right bound of rows. Then it creates a sum array of dimension equals to the column of the matrix, then find contiguous sum of each row. After that, it moves the left bound and right bound to find the max value.

Remember to switch cols and rows if rows is larger than cols.

The algorithm also uses a TreeSet. This set is used to track the previous sum within current fixed left bound and right bound. If a sum that is larger than k, we can find a smallest sum that when current sum reduce that one, it will be smaller than k.

public int maxSumSubmatrix(int[][] matrix, int k) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        if (rows == 0 || cols == 0)
            return 0;
        int maxValue = Integer.MIN_VALUE;
        
        int length, width;
        if (rows >= cols) {
            length = rows;
            width = cols;
        } else {
            length = cols;
            width = rows;
        }
        
        for (int i = 0; i < width; i++) {
            int[] sums = new int[length];
            for (int j = i; j < width; j++) {
                int currSum = 0;
                TreeSet preSum = new TreeSet<>();
                for (int z = 0; z < length; z++) {
                    sums[z] += length == cols ? matrix[j][z] : matrix[z][j];
                    currSum += sums[z];
                    if (currSum <= k) {
                        maxValue = Math.max(currSum, maxValue);
                    }
                    // when currSum is greater than k.
                    Integer dif = preSum.ceiling(currSum - k);
                    //remove previous sum to get a value that may be the max value.
                    if (dif != null) {
                        maxValue = Math.max(maxValue, currSum - dif);
                    }
                    preSum.add(currSum);
                }
            }
        }
        return maxValue;
            
    }