Tổng tối đa của hình chữ nhật Không lớn hơn K trong C ++

Giả sử chúng ta có một ma trận 2D và một số nguyên k. Chúng ta phải tìm tổng lớn nhất của một hình chữ nhật trong ma trận, sao cho tổng của nó không lớn hơn k. Vì vậy, nếu đầu vào giống như -

Và k =3, thì đầu ra sẽ là 3, vì tổng của hình chữ nhật được đánh dấu là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm maxSumSubmatrix (), hàm này sẽ lấy một ma trận mảng 2D và k,
• n:=số hàng, m:=số cột
• ans:=-inf
• để khởi tạo l:=0, khi l
• Xác định một hàng mảng Tổng kích thước n
• để khởi tạo r:=l, khi r
• để khởi tạo i:=0, khi i
• rowSum [i]:=rowSum [i] + ma trận [i, r]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

3