# Max Sum of Rectangle No Larger Than K LeetCode Solution

Here, We see Max Sum of Rectangle No Larger Than K LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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

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

``````class Solution {
public:
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];
}
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;
}
};```Code language: PHP (php)```

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

``````class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int result = Integer.MIN_VALUE;
for(int left =0 ;left<matrix[0].length; left++){
int[] rSum = new int[matrix.length];
for(int right = left;right<matrix[0].length;right++){
for(int row=0; row < matrix.length; row++)
rSum[row] += matrix[row][right];
TreeSet<Integer> set = new TreeSet<>();
int cs = 0;
for(int a: rSum){
cs += a;
Integer target = set.ceiling(cs-k);
if(target !=null)
result = Math.max(result,cs-target);
}
}
}
return result;
}
}```Code language: JavaScript (javascript)```

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

``````var maxSumSubmatrix = function(grid, k) {
let c = grid[0].length
let r = grid.length
let i, j
let dp = [...Array(r + 1)].map(e => Array(c).fill(0))
i = -1;
while (++i < r) {
j = -1;
while (++j < c)
dp[i + 1][j] = dp[i][j] + grid[i][j];
}
let res = -2147483648;
i = -1;
while (++i < r) {
let ii = i;
while (++ii < r + 1) {
j = -1;
while (++j < c) {
let tmp = 0;
let jj = j - 1;
while (++jj < c) {
tmp += dp[ii][jj] - dp[i][jj];
if (tmp == k)
return k;
if (tmp < k && res < tmp)
res = tmp;
}
}
}
}
return res;
};```Code language: JavaScript (javascript)```

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

``````class Solution(object):
def maxSumSubmatrix(self, matrix, k):
m, n = len(matrix), len(matrix[0])
max_sum = -float('inf')
for left in range(n):
temp = [0] * m
for right in range(left, n):
for i in range(m):
temp[i] += matrix[i][right]
cum_sum = 0
cum_sum_set = sorted([0])
for t in temp:
cum_sum += t
it = bisect_left(cum_sum_set, cum_sum - k)
if it != len(cum_sum_set):
max_sum = max(max_sum, cum_sum - cum_sum_set[it])
bisect.insort(cum_sum_set, cum_sum)
return max_sum``````
Scroll to Top