C++-এ K-র চেয়ে বড় নয় এমন ম্যাক্সিমাম রেক্ট্যাঙ্গেল সমasikan

ম্যাক্স সম অফ রেক্ট্যাঙ্গেল নো লার্জার دن K

একটি ২D ম্যাট্রিক্স এবং একটি পূর্ণসংখ্যা k দেওয়া আছে। ম্যাট্রিক্সের মধ্যে এমন একটি রেক্ট্যাঙ্গেল খুঁজে বের করতে হবে যার সমষ্টি k-র চেয়ে বড় নয় এবং যেটির সমষ্টি সর্বোচ্চ।

উদাহরণ:

1  0  1
0 -3  2

সমাধানের পদ্ধতি (২D ক্যাডেন + সেট)

• বাম কলাম l এবং ডান কলাম r ফিক্স করুন
• প্রতিটি সারি i-র জন্য rowSum[i] = sum(matrix[i][l..r]) গণনা করুন
• এখন ১D অ্যারে rowSum-এ সাবঅ্যারে সমষ্টি ≤ k এর সর্বোচ্চ মান খুঁজুন
  • প্রিফিক্স সম + অর্ডার্ড সেট (lower_bound) ব্যবহার করুন
  • currSum - *it ≤ k হলে আপডেট করুন
• সর্বোচ্চ মান ফেরত দিন

C++ কোড উদাহরণ

#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];
                    auto it = s.lower_bound(currSum - k);
                    if(it != s.end()) {
                        ans = max(ans, currSum - *it);
                    }
                    s.insert(currSum);
                }
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,0,1},{0,-3,2}};
    cout << (ob.maxSumSubmatrix(v, 3));
    return 0;
}

ইনপুট

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

আউটপুট

3