363. Max Sum of Rectangle No Larger Than K

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:

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

Credits:Special thanks to @fujiaozhu for adding this problem and creating all test cases.

Solution

public class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0) return Integer.MIN_VALUE;

        int row = matrix.length;
        int column = matrix[0].length;

        int bestSum = -1;
        int bestDiff = Integer.MAX_VALUE;
        for (int i = 0; i < column; i++) {
            for (int j = i; j < column; j++) {
                int[] temp = new int[row];
                for (int m = 0; m < row; m++) {
                    for (int n = i; n <= j; n++) {
                        temp[m] += matrix[m][n];
                    }
                }

                TreeSet<Integer> set = new TreeSet<>();
                int currentValue = 0;
                for (int p = 0; p < row; p++) {
                    currentValue += temp[p];

                    if (currentValue < k) {
                        if (bestDiff > k - currentValue) {
                            bestDiff = k - currentValue;
                            bestSum = currentValue;
                        }
                    } else if (currentValue == k) {
                        return currentValue;
                    }

                    try {
                        int candidate1 = set.ceiling(currentValue - k);

                        set.add(currentValue);

                        if (bestDiff > candidate1 + k - currentValue) {
                            bestSum = currentValue - candidate1;
                            bestDiff = candidate1 + k - currentValue;
                        }

                    } catch (Exception e) {
                        set.add(currentValue);


                        continue;
                    }


                }
            }
        }

        return bestSum;
    }
}