C++에서 K보다 크지 않은 직사각형의 최대 합

2D 행렬과 정수 k가 있다고 가정합니다. 합이 k보다 크지 않도록 행렬에서 직사각형의 최대 합을 찾아야 합니다. 따라서 입력이 다음과 같으면 -

그리고 k =3이면 표시된 사각형의 합이 3이므로 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• maxSumSubmatrix() 함수를 정의하면 하나의 2D 배열 행렬과 k가 필요합니다.
• n :=행 번호, m :=열 번호
• ans :=-inf
• l 초기화의 경우:=0, l
• 크기가 n인 배열 rowSum 정의
• 초기화 r :=l의 경우, r
• 초기화 i의 경우:=0, i
• rowSum[i] :=rowSum[i] + 행렬[i, r]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
      int n = matrix.size();
      int m = matrix[0].size();
      int ans = INT_MIN;
      for(int l = 0; l < m; l++){
         vector <int> rowSum(n);
         for(int r = l; r < m; r++){
            for(int i = 0; i < n; i++)rowSum[i] += matrix[i][r];
            set < int > s;
            s.insert(0);
            int currSum = 0;
            for(int i = 0; i < n; i++){
               currSum += rowSum[i];
               set <int> :: iterator it = s.lower_bound(currSum - k);
               if(it != s.end()){
                  ans = max(ans, (currSum - *it));
               }
               s.insert(currSum);
            }
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,0,1},{0,-3,2}};
   cout << (ob.maxSumSubmatrix(v, 3));
}

입력

[{1,0,1},{0,-3,2}]
3

출력

3