# Leetcode Max Sum of Rectangle No Larger Than K problem solution

In this Leetcode Max Sum of Rectangle No Larger Than K problem solution you have 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.

## Problem solution in Python.

```import bisect

def csum_less_than_k(nums, k):
ans = float('-inf')
slist = [0]

for x in range(1, len(nums)):
nums[x] += nums[x-1]

for p in nums:
idx = bisect.bisect_left(slist, p-k)
if idx < len(slist):
ans = max(ans, p-slist[idx])

bisect.insort(slist, p)

return ans

class Solution:
def maxSumSubmatrix(self, matrix, k: int) -> int:
R = len(matrix)
C = len(matrix[0])
ans = float('-inf')
for r in range(R):
for c in range(1, C):
matrix[r][c] += matrix[r][c-1]

for left_edge in range(C):
for right_edge in range(left_edge, C):
ledge = lambda i: matrix[i][left_edge-1] if left_edge > 0 else 0
one_d_array = [matrix[i][right_edge]-ledge(i) for i in range(R)]
ans = max(ans, csum_less_than_k(one_d_array, k))

return ans
```

## Problem solution in Java.

```class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int[][] prefixSums = calculatePrefixSums(matrix);
return maxSum(prefixSums, k);
}

private int maxSum(int[][] prefixSums, int k) {
int n = prefixSums.length;
int m = prefixSums[0].length;

for (int x = 1; x < m; x++) {
for (int l = 0; l < x; l++) {
TreeSet<Integer> set = new TreeSet<>();

for (int y = 1; y < n; y++) {
int totalSum = prefixSums[y][x] - prefixSums[y][l];
Integer previous = set.ceiling(totalSum - k);

if (previous != null) {
}

}
}
}

}

private int[][] calculatePrefixSums(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
int[][] prefixSums = new int[n + 1][m + 1];

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

return prefixSums;
}
}
```

## Problem solution in C++.

```class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int n = matrix.size() ;
int m = matrix[0].size();
int temp[n];
memset(temp,0,sizeof temp);
bool does = false;
int maxx = INT_MAX;
for(int i = 0 ; i < matrix.size() ; ++i){
for(int j = 0 ; j < matrix[0].size() ; ++j){
if(matrix[i][j] >= 0) does = true;
maxx = max(maxx , matrix[i][j]);
}
}
if(does == false){
return maxx;
}
int maxsum = INT_MIN;
for(int left = 0 ; left < m ; ++left){
for(int right = left ; right < m ; ++right){
if(left == right){
memset(temp , 0 , sizeof temp);
}
for(int i = 0 ; i < n ; ++i){
temp[i]+=matrix[i][right];
}

int currsum = 0 ;
set<int> s;
s.insert(0);
for(int i = 0 ; i < n ; ++i){
currsum+=temp[i];
int req = currsum - k;
auto it = s.lower_bound(req);
if(it != s.end()){
maxsum = max(maxsum , currsum - *it);
}
s.insert(currsum);
}
}
}
return maxsum;
}
};
```