# Max Sum of Rectangle No Larger Than K – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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 = 2Output:2Explanation: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 = 3Output:3

**Constraints:**

`m == matrix.length`

`n == matrix[i].length`

`1 <= m, n <= 200`

`-100 <= matrix[i][j] <= 100`

`-10`

^{5}<= k <= 10^{5}

# C++ Max Sum of Rectangle No Larger Than K LeetCode Solution

```
``````
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
if (matrix.empty()) return 0;
int row = matrix.size(), col = matrix[0].size(), res = INT_MIN;
for (int l = 0; l < col; ++l) {
vector<int> sums(row, 0);
for (int r = l; r < col; ++r) {
for (int i = 0; i < row; ++i) {
sums[i] += matrix[i][r];
}
// Find the max subarray no more than K
set<int> accuSet;
accuSet.insert(0);
int curSum = 0, curMax = INT_MIN;
for (int sum : sums) {
curSum += sum;
set<int>::iterator it = accuSet.lower_bound(curSum - k);
if (it != accuSet.end()) curMax = std::max(curMax, curSum - *it);
accuSet.insert(curSum);
}
res = std::max(res, curMax);
}
}
return res;
}
```

# Java Max Sum of Rectangle No Larger Than K LeetCode Solution

```
``````
public int maxSumSubmatrix(int[][] matrix, int target) {
int row = matrix.length;
if(row==0)return 0;
int col = matrix[0].length;
int m = Math.min(row,col);
int n = Math.max(row,col);
//indicating sum up in every row or every column
boolean colIsBig = col>row;
int res = Integer.MIN_VALUE;
for(int i = 0;i<m;i++){
int[] array = new int[n];
// sum from row j to row i
for(int j = i;j>=0;j--){
int val = 0;
TreeSet<Integer> set = new TreeSet<Integer>();
set.add(0);
//traverse every column/row and sum up
for(int k = 0;k<n;k++){
array[k]=array[k]+(colIsBig?matrix[j][k]:matrix[k][j]);
val = val + array[k];
//use TreeMap to binary search previous sum to get possible result
Integer subres = set.ceiling(val-target);
if(null!=subres){
res=Math.max(res,val-subres);
}
set.add(val);
}
}
}
return res;
}
```

# Python 3 Max Sum of Rectangle No Larger Than K LeetCode Solution

```
```For each row, calculate the prefix sum. For each pair of columns, calculate the sum of rows.

Now this problem is changed to a 1D problem: max subarray sum no more than k.

```
def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
def maxSumSubarray(arr):
sub_s_max = float('-inf')
s_curr = 0
prefix_sums = [float('inf')]
for x in arr:
bisect.insort(prefix_sums, s_curr)
s_curr += x
i = bisect.bisect_left(prefix_sums, s_curr - k)
sub_s_max = max(sub_s_max, s_curr - prefix_sums[i])
return sub_s_max
m, n = len(matrix), len(matrix[0])
for x in range(m):
for y in range(n - 1):
matrix[x][y+1] += matrix[x][y]
res = float('-inf')
for y1 in range(n):
for y2 in range(y1, n):
arr = [matrix[x][y2] - (matrix[x][y1-1] if y1 > 0 else 0) for x in range(m)]
res = max(res, maxSumSubarray(arr))
return res
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1