ผลรวมสูงสุดของสี่เหลี่ยมผืนผ้าไม่เกิน K ใน C++

สมมติว่าเรามีเมทริกซ์ 2 มิติ และจำนวนเต็ม k เราต้องหาผลรวมสูงสุดของสี่เหลี่ยมจัตุรัสในเมทริกซ์ โดยที่ผลรวมของมันจะต้องไม่เกิน k ดังนั้นหากอินพุตเป็นเช่น −

และ k =3 ผลลัพธ์จะเป็น 3 เนื่องจากผลรวมของสี่เหลี่ยมที่ทำเครื่องหมายไว้คือ 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน maxSumSubmatrix() ซึ่งจะใช้เมทริกซ์อาร์เรย์ 2 มิติและ k
• n :=หมายเลขแถว m :=หมายเลขคอลัมน์
• ตอบ :=-inf
• สำหรับการเริ่มต้น l :=0 เมื่อ l
• กำหนดอาร์เรย์แถวผลรวมของขนาด n
• สำหรับการเริ่มต้น r :=l เมื่อ r
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• rowSum[i] :=rowSum[i] + matrix[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