Question

Formatted question description: https://leetcode.ca/all/363.html

 363	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:

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

 @tag-queue

Algorithm

To establish a cumulative sum, refer to the previous question Range Sum Query 2D-Immutable, which can quickly find any interval sum.

When traversing to (i, j), calculate sum(i, j), which represents the sum of the rectangle (0, 0) to (i, j), and then traverse all the sub-rectangles in this rectangle, and calculate the sum and phase K Compared with this, it can traverse all the sub-rectangles of the original rectangle.

Code

Java

import java.util.TreeSet;

public class Max_Sum_of_Rectangle_No_Larger_Than_K {


    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,
                res = Integer.MIN_VALUE;
            int[][] sum = new int[m][n]; // sum of the rectangle (0, 0) to (i, j)
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int area = matrix[i][j];
                    if (i > 0) area += sum[i - 1][j];
                    if (j > 0) area += sum[i][j - 1];
                    if (i > 0 && j > 0) area -= sum[i - 1][j - 1];
                    sum[i][j] = area;

                    for (int r = 0; r <= i; ++r) {
                        for (int c = 0; c <= j; ++c) {
                            int d = sum[i][j];
                            if (r > 0) d -= sum[r - 1][j];
                            if (c > 0) d -= sum[i][c - 1];
                            if (r > 0 && c > 0) d += sum[r - 1][c - 1];
                            if (d <= k) res = Math.max(res, d);
                        }
                    }
                }
            }
            return res;
        }
    }

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

            int m = matrix.length;
            int n = matrix[0].length;

            int[][] preSum = new int[m][n + 1];

            for (int i = 0; i < m; i++) {
                for (int j = 1; j <= n; j++) {
                    preSum[i][j] = preSum[i][j - 1] + matrix[i][j - 1];
                }
            }

            int ans = Integer.MIN_VALUE;
            for (int c1 = 1; c1 <= n; c1++) {
                for (int c2 = c1; c2 <= n; c2++) {
                    int[] preSumRow = new int[m];
                    for (int row = 0; row < m; row++) {
                        preSumRow[row] = preSum[row][c2] - preSum[row][c1 - 1];
                    }

                    ans = Math.max(ans, getMaxSubarrayHelper(preSumRow, k));
                }
            }

            return ans;
        }

        private int getMaxSubarrayHelper(int[] nums, int target) {
            TreeSet<Integer> treeSet = new TreeSet<>();

            int ans = Integer.MIN_VALUE;
            int[] preSum = new int[nums.length + 1];

            for (int i = 1; i <= nums.length; i++) {
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }

            treeSet.add(0);
            for (int i = 1; i <= nums.length; i++) {
                Integer num = preSum[i] - target;
                Integer ceiling = treeSet.ceiling(num);

                if (ceiling != null) {
                    ans = Math.max(ans, preSum[i] - ceiling);
                }

                treeSet.add(preSum[i]);
            }

            return ans;
        }
    }
}

All Problems

All Solutions