LeetCode //C - 363. Max Sum of Rectangle No Larger Than K

363. Max Sum of Rectangle No Larger Than K

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.length
  
• 1 <= m, n <= 100
  
• -100 <= matrix[j] <= 100
  
•                                         −                            1                                       0                               5                                      <                            =                            k                            <                            =                            1                                       0                               5                                            -10^5 <= k <= 10^5                     −105<=k<=105
  

From: LeetCode
Link: 363. Max Sum of Rectangle No Larger Than K

---

Solution:

Ideas:

• Outer loops: We loop over all pairs of starting and ending rows.
  
• Column sum array: We calculate the cumulative sums for columns between the two rows, effectively reducing the 2D matrix to a 1D array problem.
  
• Brute-force subarray sum check: We calculate all possible sums of subarrays in the 1D colSums array and track the largest one that is no larger than k.
  

Code:

1. int maxSumSubmatrix(int** matrix, int matrixSize, int* matrixColSize, int k) {
2.     int maxSum = INT_MIN;
3.     int rows = matrixSize, cols = *matrixColSize;
5.     // Loop through the possible row start points
6.     for (int startRow = 0; startRow < rows; ++startRow) {
7.         // Temporary array to store column sums
8.         int* colSums = (int*)calloc(cols, sizeof(int));
9.         
10.         // Loop through the possible row end points
11.         for (int endRow = startRow; endRow < rows; ++endRow) {
12.             // Update column sums
13.             for (int col = 0; col < cols; ++col) {
14.                 colSums[col] += matrix[endRow][col];
15.             }
17.             // Now we need to find the subarray no larger than k in the colSums array
18.             // Brute-force approach for subarray sums
19.             for (int startCol = 0; startCol < cols; ++startCol) {
20.                 int currentSum = 0;
21.                 for (int endCol = startCol; endCol < cols; ++endCol) {
22.                     currentSum += colSums[endCol];
23.                     if (currentSum <= k) {
24.                         if (currentSum > maxSum) {
25.                             maxSum = currentSum;
26.                         }
27.                     }
28.                 }
29.             }
30.         }
31.         free(colSums);
32.     }
34.     return maxSum;
35. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。