C++-এ সম K হলে সবচেয়ে বড় আয়তাকার সাব-ম্যাট্রিক্স খুঁজে বের করা

সমস্যা

২D ম্যাট্রিক্স mat এবং মান K দেওয়া। যেটির যোগফল K এর সমান, এমন সবচেয়ে বড় এলাকায় ফੈले আয়তাকার সাব-ম্যাট্রিক্স খুঁজে বের করুন।

অ্যালগরিদম: কলাম পেয়ার + সাবঅ্যারে সম = K

1. প্রতিটি বাম কলাম left (০ থেকে col-1) এর জন্য:
   • একটি টেম্প অ্যারে temp[row] ০ দিয়ে ইনিশিয়ালাইজ করুন।
   • দায় কলাম right (left থেকে col-1) পর্যন্ত বাড়ান:
     • প্রতিটি সারি i-এ mat[i][right] যোগ করুন temp[i]-তে।
     • এখন temp ১D অ্যারে। এর মধ্যে সাবঅ্যারে যার সম = K, সেটি খুঁজুন (হ্যাশ ম্যাপ দিয়ে O(n))।
     • পাওয়া গেলে এলাকা = (down-up+1) * (right-left+1)। ম্যাক্সিমাম আপডেট করুন।

হেল্পার: সাবঅ্যারে সম = K (হ্যাশ ম্যাপ)

bool sum_k(int arr[], int& start, int& end, int n, int k) {
    unordered_map<int,int> mp;
    int sum = 0, max_len = 0;
    for (int i=0; i

C++ মূল ফাংশন (সংক্ষিপ্ত)
void sum_zero(vector<vector<int>> &mat, int k) {
    int row = mat.size(), col = mat[0].size();
    vector<int> temp(row), final_point(4,0);
    int maxArea = INT_MIN;
    for (int left=0; left maxArea) {
                    maxArea = area;
                    final_point = {up, down, left, right};
                }
            }
        }
    }
    // প্রিন্ট ফাইনাল পয়েন্ট ও সাব-ম্যাট্রিক্স
}

উদাহরণ আউটপুট
(Top, Left) Coordinate: (1, 0)
(Bottom, Right) Coordinate: (3, 2)
-7 7 8
11 -14 4
-4 3 1