Max Sum of Rectangle No Larger Than K
Post
Cancel

# LeetCode #363: Max Sum of Rectangle No Larger Than K (C/C++).

hard

source: https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/
C/C++ Solution to LeetCode problem 363. Max Sum of Rectangle No Larger Than K.

## Problem

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.

## Examples

### 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[i].length
• 1 <= m, n <= 100
• -100 <= matrix[i][j] <= 100
• -105 <= k <= 105

## Solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 class Solution { public: int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { int rows = matrix.size(); int cols = matrix[0].size(); bool end = false; int max = -INT_MAX; for (int r = 0; r < rows; r += 1) { int cSum = 0; for (int c = 0; c < cols; c += 1) { cSum += matrix[r][c]; matrix[r][c] = r == 0 ? cSum : (cSum + matrix[r - 1][c]); for (int r1 = r; r1 >= 0; r1 -= 1) { for (int c1 = c; c1 >= -1; c1 -= 1) { int tmp = matrix[r][c]; if (c1 == c && r1 == r) {} else { if (r == 0 && c1 != c && c1 >= 0) { tmp -= matrix[r][c1]; } else { if (c > 0 && c1 >= 0) tmp -= matrix[r][c1]; if (r > 0 && r1 >= 0) tmp -= matrix[r1][c]; if (c > 0 && r > 0 && r1 >= 0 && c1 >= 0) tmp += matrix[r1][c1]; } } if (tmp >= max && tmp <= k) { max = tmp; } if (max == k) { end = true; break; } } if (end) break; } if (max == k) { end = true; break; } } if (end) break; } return max; } };