# introduce

My LeetCode homepage, one problem one solution

Tags: queue, dynamic programming, binary search

363. The rectangular area does not exceed the maximum value of K and
Difficulty difficulty

# subject

Give you a matrix of m x n and an integer k, find out and return the maximum sum of values not exceeding K in the rectangular area inside the matrix.

The title data ensures that there will always be a rectangular area with a value and no more than k.

Example 1:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: the sum of the values of the rectangular area [[0,1], [- 2,3]] circled by the blue border is 2, and 2 is the maximum number not exceeding K (k = 2).

Example 2:

Input: matrix = [[2,2,-1]], k = 3
Output: 3

Tips:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -100 <= matrix[i][j] <= 100
• -105 <= k <= 105

Advanced: how to design a solution if the number of rows is much larger than the number of columns?

# Understand the topic

The title gives a matrix and an integer k

Among them, we need a sub matrix, which meets the following requirements:

• Where the sum of elements is less than K
• Not only should it be less than k, but also all the matrices that satisfy the element and maximum of condition one

# Analysis topic

Through the analysis of the problem, we can see that the prefix and can be used to solve this problem

Why do you think so? Because I've done it before 304. Two dimensional area and retrieval - matrix immutable (my problem solution)

It is also a rectangle to calculate the area. In this way, the operation time can be reduced by prefix and

If the traversal problem 304 can be used directly

Here I define two coordinate points of the submatrix for later explanation

## Since you want to use prefix and, you always need to initialize first

That is, calculate the sum of the elements of each submatrix when (x1,y1) is (0,0)

```int[][] sum = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1]
- sum[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
```

# Naive prefix and

Directly use 4-fold loop to traverse each sub matrix. The time complexity is O (m ^ 2 * n ^ 2), but it will probably time out, so it only means

```// Pointing submatrix x1
for (int i = 1; i <= m; i++) {
// y1 pointing to submatrix
for (int j = 1; j <= n; j++) {
// x2 pointing to submatrix
for (int p = i; p <= m; p++) {
// y2 pointing to submatrix
for (int q = j; q <= n; q++) {
// Quadruple cyclic ergodic submatrix
}
}
}
}
```

# Prefix and + dichotomy

## Using TreeSet ceiling()

The submatrix corresponds to four edges. When we fix three of them, can we get the last one in a simpler way?

The main problem is that there are elements with negative weight, which destroys the order of the array, and the use of dichotomy is not very reasonable

So is there a solution?

The results are given directly here. To see the derivation process, please see Teacher Miyazawa Sanya's explanation

• Use TreeSet to maintain all right boundaries traversed
• Use the ceiling() method to return the smallest element greater than or equal to the given element
• If it exists, give two points
• If it doesn't exist, go back
• In conclusion, this method first traverses to obtain the right boundary, and then looks for the value that can become the left boundary in the traversed boundary
• Optimization is to use TreeSet, an ordered set based on red and black trees, so that the acquisition time of the last edge is O(log n)

Here is a picture of Mr. Miyoshi Sanye:

In the figure, it means to fix the upper, lower and right boundaries, and binary search the left boundary

### Corresponding code

This code is the first version of Ms. Miyoshi Sanye's code. For the optimized version, please also see Ms. Miyoshi Sanye's problem solution

```class Solution {
public int maxSumSubmatrix(int[][] mat, int k) {
int m = mat.length, n = mat[0].length;

// Preprocessing prefix and
int[][] sum = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
}
}

int ans = Integer.MIN_VALUE;
// Upper boundary of ergodic submatrix
for (int top = 1; top <= m; top++) {
// Ergodic lower boundary of submatrix
for (int bot = top; bot <= m; bot++) {
// Use "ordered set" to maintain all right boundaries traversed
TreeSet<Integer> ts = new TreeSet<>();
// Add an initial value to the ordered set
ts.add(0);
// Ergodic right boundary of submatrix
for (int r = 1; r <= n; r++) {
// Calculate right by prefix and
int right = sum[bot][r] - sum[top - 1][r];
// Find left by two points
Integer left = ts.ceiling(right - k);
if (left != null) {
// If left exists, it means that the dichotomy has a left boundary that meets the conditions. At this time, the result is updated
int cur = right - left;
ans = Math.max(ans, cur);
}
// Add the traversed right to the ordered set
ts.add(right);
}
}
}
return ans;
}
}
```

## Using auxiliary arrays

• Fix the left and right boundaries (of course, fixing the upper and lower boundaries is the same)
• Set up the auxiliary array rowSum [], which stores the matrix elements and of each row between the two boundaries

Here I borrow lzhlyle's picture

It should be clear at this time:

The sum of rowSum continuous subarrays is the sum of rectangular elements corresponding to the upper and lower boundaries

At this time, the problem is to find the maximum subarray of elements and less than k in rowSum []

1. Double loop Traversal Solution

2. reference 53. Maximum subsequence sum Solution in:

```public int maxSubArray(int[] nums) {
int len = nums.length, max, dp;
if (len == 0) return 0;
// To be as big as possible, try not to be negative
dp = max = nums[0];
for (int i = 1; i < len; i++) {
// The previous and are smaller than the current ones. What else should we do
dp = Math.max(dp, dp +  nums[i]);
// Update max
max = Math.max(max, dp);
}
return max;
}
```

At this time, analyze the relationship between the returned max and k:

• If Max is still less than k, it will be directly updated to the final result: res = math max(max, res);

• If max is larger than k, then traverse rowSum [], and update all traversed results less than k to res

```for (int a = 0; a < row; a++) {
int currSum = 0;
for (int b = a; b < row; b++) {
currSum += sum[b];
if (currSum <= k)
res = Math.max(currSum, res);
}
}
```

### Corresponding code

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

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

int res = Integer.MIN_VALUE;

// Fixed left and right boundaries
for (int i = 0; i < col; i++) {// Enumeration left boundary
int[] sum = new int[row];
for (int j = i; j < col; j++) {// Enumeration right boundary
// Sum only for rows
for (int r = 0; r < row; r++) {
sum[r] += matrix[r][j];
}

int dp = 0;
int max = sum[0];
for (int n : sum) {
// The previous and are smaller than the current ones. What else should we do
dp = Math.max(n, dp + n);
// Update max
max = Math.max(dp, max);
// If the maximum is found to be k, return k directly
if (max == k)
return max;
}

if (max < k) {
res = Math.max(max, res);
}
else {
for (int a = 0; a < row; a++) {
int currSum = 0;
for (int b = a; b < row; b++) {
currSum += sum[b];
if (currSum <= k)
res = Math.max(currSum, res);
}
}
// If the maximum is found to be k, return k directly
if (res == k) return res;
}
}
}
return res;
}
}
```

# Thank you for your reference:

Teacher lzhlyle's Java, optimize from violence, with drawings and notes

Added by Piba on Wed, 02 Mar 2022 01:12:42 +0200