मान लीजिए हमारे पास एक 2D मैट्रिक्स mat और एक मान 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 |
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- MAX := 100
- sum_k() नामक एक फंक्शन परिभाषित करें, जो एक ऐरे arr, स्टार्ट, एंड, n, k लेता है:
- एक मैप परिभाषित करें
- सम := 0, मैक्सिमम_लेंथ := 0
- i := 0 से n-1 तक लूप करें:
- सम := सम + arr[i]
- यदि सम K के बराबर है: मैक्सिमम_लेंथ := i + 1, स्टार्ट := 0, एंड := i
- यदि सम मैप में नहीं है: मैप[सम] := i
- यदि (सम - k) मैप में है: यदि मैक्सिमम_लेंथ < (i - मैप[सम - k]), तो मैक्सिमम_लेंथ, स्टार्ट, एंड अपडेट करें
- यदि मैक्सिमम_लेंथ 0 नहीं है तो true लौटाएं
- मेन मेथड से:
- रो := mat की पंक्ति संख्या, कॉल := mat की स्तंभ संख्या
- आकार रो का एक ऐरे temp परिभाषित करें
- फाइनल_पॉइंट = {0,0,0,0} ऐरे परिभाषित करें
- मैक्सएरिया := -inf
- लेफ्ट := 0 से कॉल-1 तक लूप करें:
- temp को 0 से भरें
- राइट := लेफ्ट से कॉल-1 तक लूप करें:
- i := 0 से रो-1 तक लूप करें: temp[i] := temp[i] + mat[i][राइट]
- सम := sum_k(temp, अप, डाउन, रो, k)
- क्षेत्रफल := (डाउन - अप + 1) * (राइट - लेफ्ट + 1)
- यदि सम शून्येतर है और मैक्सएरिया < क्षेत्रफल: फाइनल_पॉइंट और मैक्सएरिया अपडेट करें
- यदि फाइनल_पॉइंट [0,0,0,0] है और mat[0][0] K नहीं है, तो "No sub-matrix found" लौटाएं
- टॉप-लेफ्ट पॉइंट (फाइनल_पॉइंट[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
