Home 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:

Matrix example

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;
  }
};
This post is licensed under CC BY 4.0 by the author.

Range Sum Query 2D - Immutable

Continuous Subarray Sum