Max Sum of Rectangle No Larger Than K LeetCode solution in C++

1
class Solution {
2
 public:
3
  // function for finding maximum subarray having sum less than k
4

5
  int find_max(vector<int> &arr, int k) {
6
    int n = arr.size();
7

8
    int maxi = INT_MIN;
9

10
    // curr_sum will store cumulative sum
11

12
    int curr_sum = 0;
13

14
    // set will store the prefix sum of array
15

16
    set<int> s;
17

18
    // put 0 into set, if curr_sum == k, (curr_sum - k) will be zero
19

20
    s.insert(0);
21

22
    for (int i = 0; i < n; i++) {
23
      // calculate cumulative sum
24

25
      curr_sum += arr[i];
26

27
      // find the prefix sum in set having sum == curr_sum - k
28

29
      auto it = s.lower_bound(curr_sum - k);
30

31
      // if prefix sum is present, update the maxi
32

33
      if (it != s.end()) {
34
        maxi = max(maxi, curr_sum - *it);
35
      }
36

37
      // insert prefix sum into set
38

39
      s.insert(curr_sum);
40
    }
41

42
    return maxi;
43
  }
44

45
  int maxSumSubmatrix(vector<vector<int>> &matrix, int k) {
46
    int n = matrix.size();
47

48
    int m = matrix[0].size();
49

50
    int maxi = INT_MIN;
51

52
    // fix the position two two rows and take cumulative sum of columns between
53
    // two fixed rows
54

55
    for (int start_row = 0; start_row < n; start_row++) {
56
      vector<int> col_array(m, 0);
57

58
      for (int end_row = start_row; end_row < n; end_row++) {
59
        // take cumulative sum of columns between two fixed rows
60

61
        for (int col = 0; col < m; col++) {
62
          col_array[col] += matrix[end_row][col];
63
        }
64

65
        // find maximum subarray having sum less than equal to k
66

67
        int curr_max = find_max(col_array, k);
68

69
        // update the maximum sum
70

71
        maxi = max(maxi, curr_max);
72
      }
73
    }
74

75
    return maxi;
76
  }
77
};