363 Max Sum of Rectangle No Larger Than K

363. Max Sum of Rectangle No Larger Than K

1. Question

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?

2. Implementation

(1) DP + Binary Search

思路:

(1) 找出所有可能submatrix,这里利用一个技巧是建立一个rowSum数组，存储每个submatrix的row的和。我们利用两个for loop从左到右先固定每个submatrix的两列，然后在从上到下扫行，得到submatrix的sum

(2) 对每个rowSum, 其作用就类似于1维数组中的prefixSum，由于题目要找出submatrix 的sum要小于等于k的，而位于行i和j之间的submatrix的sum就等于rowSum[j] - rowSum[i - 1]。 也即我们要找到一个rowSum, 它的值是小于等于 rowSum[j] - k的。这可以利用二分法找这个rowSum的右边界。这里我们利用treeSet这个数据结构，方便我们找到这个值。这个做法和Minimum Subarray那道题利用prefixSum数组的二分法的思想相同

(3) 如果找到这个rowSum, 则我们可以得到submatrix的sum，然后以此找到小于等于K的最大的submatrix和

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

        int m = matrix.length, n = matrix[0].length;
        int res = Integer.MIN_VALUE;

        for (int leftCol = 0; leftCol < n; leftCol++) {
            int[] rowSum = new int[m];

            for (int rightCol = leftCol; rightCol < n; rightCol++) {

                for (int i = 0; i < m; i++) {
                    rowSum[i] += matrix[i][rightCol];
                }

                TreeSet<Integer> set = new TreeSet<>();
                set.add(0);
                int prefixSum = 0;

                for (int sum : rowSum) {
                    prefixSum += sum;
                    Integer num = set.ceiling(prefixSum - k);
                    if (num != null) {
                        res = Math.max(res, prefixSum - num);
                    }
                    set.add(prefixSum);
                }
            }
        }
        return res;
    }
}

(2) Kadane Algorithm优化

思想: 这里的优化用Maximum Subarray里的kadane algorithm, 在我们遍历每个submatrix的的同时，我们利用maximum subarray的思路找出当前submatrix的最大值，如果该最大值小于等于K,则我们直接与res比较，而不必要通过treeSet，找到符合条件的submatrix sum

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

        int m = matrix.length, n = matrix[0].length;
        int res = Integer.MIN_VALUE;

        for (int leftCol = 0; leftCol < n; leftCol++) {
            int[] rowSum = new int[m];

            for (int rightCol = leftCol; rightCol < n; rightCol++) {
                int maxSum = Integer.MIN_VALUE;
                int curMaxSum = 0;

                for (int i = 0; i < m; i++) {
                // Optimization with Kadane Algorithm
                    rowSum[i] += matrix[i][rightCol];
                    curMaxSum = Math.max(rowSum[i], curMaxSum + rowSum[i]);
                    maxSum = Math.max(maxSum, curMaxSum);
                }

                if (maxSum <= k) {
                    res = Math.max(maxSum, res);
                    continue;
                }

                TreeSet<Integer> set = new TreeSet<>();
                set.add(0);
                int prefixSum = 0;

                for (int sum : rowSum) {
                    prefixSum += sum;
                    Integer num = set.ceiling(prefixSum - k);
                    if (num != null) {
                        res = Math.max(res, prefixSum - num);
                    }
                    set.add(prefixSum);
                }
            }
        }
        return res;
    }
}

3. Time & Space Complexity

DP + Binary Search: 时间复杂度O(mlogm * n^2), 空间复杂度O(m)

Kadane Algorithm优化: 时间复杂度O(mlogm * n^2), 空间复杂度O(m)