Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/363.html
Given an m x n
matrix matrix
and an integer k
, return the max sum of a rectangle in the matrix such that its sum is no larger than k
.
It is guaranteed that there will be a rectangle with a sum no larger than k
.
Example 1:
Input: matrix = [[1,0,1],[0,-2,3]], k = 2 Output: 2 Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).
Example 2:
Input: matrix = [[2,2,-1]], k = 3 Output: 3
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-105 <= k <= 105
Follow up: What if the number of rows is much larger than the number of columns?
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
-
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; } } }
-
// OJ: https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/ // Time: O(M^2 * NlogN) // Space: O(N) class Solution { public: int maxSumSubmatrix(vector<vector<int>>& A, int k) { int M = A.size(), N = A[0].size(), ans = INT_MIN; for (int i = 0; i < M; ++i) { // starting row vector<int> prefix(N, 0); for (int j = i; j < M; ++j) { // ending row int sum = 0; set<int> s{0}; for (int t = 0; t < N; ++t) { sum += A[j][t]; prefix[t] += sum; int target = prefix[t + 1] - k; auto it = s.lower_bound(target); if (it != s.end()) { ans = max(ans, prefix[t] - *it); } s.insert(prefix[t]); } } } return ans; } };
-
import bisect class Solution(object): def maxSumSubmatrix(self, matrix, k): """ :type matrix: List[List[int]] :type k: int :rtype: int """ ans = float("-inf") dp = [[0] * len(matrix[0]) for _ in range(len(matrix))] for i in range(0, len(matrix)): for j in range(0, len(matrix[0])): dp[i][j] = dp[i][j - 1] + matrix[i][j] for start in range(0, len(matrix[0])): for end in range(start, len(matrix[0])): sums = [0] subsum = 0 for i in range(0, len(matrix)): if start > 0: subsum += dp[i][end] - dp[i][start - 1] else: subsum += dp[i][end] idx = bisect.bisect_left(sums, subsum - k) if idx < len(sums): ans = max(ans, subsum - sums[idx]) bisect.insort(sums, subsum) return ans