ধরুন আমাদের একটি 2D ম্যাট্রিক্স ম্যাট এবং একটি মান K আছে, আমাদেরকে দীর্ঘতম আয়তক্ষেত্রাকার সাবম্যাট্রিক্স খুঁজে বের করতে হবে যার যোগফল K এর সমান।
সুতরাং, যদি ইনপুট মত হয়
| 2 | 8 | -5 | 6 |
| -7 | 7 | 8 | -3 |
| 11 | -14 | 4 | ৷3 |
| -4 | 3 | 1 | ৷10 |
এবং K =9
তাহলে আউটপুট হবে উপরের-বাম বিন্দু হল (1, 0) এবং নীচের-ডান বিন্দু হবে (3, 2)।
| -7 | 7 | 8 |
| 11 | -14 | 4 | ৷
| -4 | 3 | 1 | ৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
সর্বোচ্চ :=100
-
একটি ফাংশন সংজ্ঞায়িত করুন sum_k(), এটি একটি অ্যারে অ্যারের, শুরু, শেষ, n, k,
লাগবে -
একটি মানচিত্র সংজ্ঞায়িত করুন
-
যোগফল :=0, সর্বোচ্চ_দৈর্ঘ্য :=0
-
আরম্ভ করার জন্য i :=0, যখন i
-
যোগফল :=যোগফল + arr[i]
-
যদি যোগফল k এর সমান হয়, তাহলে −
-
সর্বাধিক_দৈর্ঘ্য :=i + 1
-
শুরু :=0
-
শেষ :=i
-
-
যদি যোগফল মানচিত্রে না থাকে, তাহলে -
-
মানচিত্র[সমষ্টি] :=i
-
-
যদি (সমষ্টি - k) মানচিত্রে থাকে, তাহলে −
-
যদি সর্বাধিক_দৈর্ঘ্য <(i - মানচিত্র[সমষ্টি - k]), তাহলে −
-
সর্বাধিক_দৈর্ঘ্য :=i - মানচিত্র[সমষ্টি - k]
-
শুরু :=মানচিত্র[সমষ্টি - কে] + 1
-
শেষ :=i
-
-
-
-
সর্বাধিক_দৈর্ঘ্য 0 না হলে সত্য ফেরত দিন
-
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
-
সারি :=ম্যাটের সারি গণনা, col :=ম্যাটের কলাম গণনা
-
আকারের একটি অ্যারে তাপমাত্রা সংজ্ঞায়িত করুন:সারি।
-
একটি অ্যারে চূড়ান্ত_পয়েন্ট ={0,0,0,0}
সংজ্ঞায়িত করুন -
maxArea :=-inf
-
বাম আরম্ভ করার জন্য :=0, যখন বামে
-
0
দিয়ে তাপমাত্রা পূরণ করুন -
ডানে শুরু করার জন্য :=বাম, যখন ডান
-
আরম্ভ করার জন্য i :=0, যখন i
-
temp[i] :=temp[i] + mat[i, right]
-
-
যোগফল :=sum_k(temp, up, down, row, k)
-
এলাকা :=(নিচে - উপরে + 1) * (ডান - বাম + 1)
-
যদি যোগফল অ-শূন্য হয় এবং maxArea <এলাকা, তাহলে −
-
ফাইনাল_পয়েন্ট[0] :=উপরে, ফাইনাল_পয়েন্ট[1] :=নিচে
-
ফাইনাল_পয়েন্ট[2] :=বাম, ফাইনাল_পয়েন্ট[3] :=ডান
-
maxArea :=এলাকা
-
-
-
যদি চূড়ান্ত_বিন্দু হয় [0,0,0,0] এবং ম্যাট[0,0] হয় k না হয়, তাহলে
-
"কোন সাব-ম্যাট্রিক্স পাওয়া যায়নি"
ফেরত দিন
-
-
-
উপরের-বাম বিন্দু প্রদর্শন করুন (ফাইনাল_পয়েন্ট[0], ফাইনাল_পয়েন্ট[2])
-
নীচে-ডান বিন্দু প্রদর্শন করুন (ফাইনাল_পয়েন্ট[1], ফাইনাল_পয়েন্ট[3])
-
প্রদর্শন মাদুর উপাদান.
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
bool sum_k(int arr[], int& start, int& end, int n, int k) {
unordered_map<int, int> map;
int sum = 0, maximum_length = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == k) {
maximum_length = i + 1;
start = 0;
end = i;
}
if (map.find(sum) == map.end())
map[sum] = i;
if (map.find(sum - k) != map.end()) {
if (maximum_length < (i - map[sum - k])) {
maximum_length = i - map[sum - k];
start = map[sum - k] + 1;
end = i;
}
}
}
return (maximum_length != 0);
}
void sum_zero(vector<vector<int>> &mat, int k) {
int row = mat.size();
int col = mat[0].size();
int temp[row], area;
bool sum;
int up, down;
vector<int> final_point = {0,0,0,0};
int maxArea = INT_MIN;
for (int left = 0; left < col; left++) {
memset(temp, 0, sizeof(temp));
for (int right = left; right < col; right++) {
for (int i = 0; i < row; i++)
temp[i] += mat[i][right];
sum = sum_k(temp, up, down, row, k);
area = (down - up + 1) * (right - left + 1);
if (sum && maxArea < area) {
final_point[0] = up;
final_point[1] = down;
final_point[2] = left;
final_point[3] = right;
maxArea = area;
}
}
}
if (final_point[0] == 0 && final_point[1] == 0 && final_point[2] == 0 &&
final_point[3] == 0 && mat[0][0] != k) {
cout << "No sub-matrix found";
return;
}
cout << "(Top, Left) Coordinate: " << "(" << final_point[0] << ", " << final_point[2] << ")" << endl;
cout << "(Bottom, Right) Coordinate: " << "(" << final_point[1] << ", " << final_point[3] << ")" << endl;
for (int j = final_point[0]; j <= final_point[1]; j++) {
for (int i = final_point[2]; i <= final_point[3]; i++)
cout << mat[j][i] << " ";
cout << endl;
}
}
main(){
vector<vector<int>> v = {
{ 2, 8, -5, 6 },
{ -7, 7, 8, -3 },
{ 11, -14, 4, 3 },
{ -4, 3, 1, 10 }};
sum_zero(v, 9);
} ইনপুট
{{ 2, 8, -5, 6 },
{ -7, 7, 8, -3 },
{ 11, -14, 4, 3 },
{ -4, 3, 1, 10 }},
9 আউটপুট
(Top, Left) Coordinate: (1, 0) (Bottom, Right) Coordinate: (3, 2) -7 7 8 11 -14 4 -4 3 1
