सबसे बड़ा क्षेत्रफल आयताकार उप-मैट्रिक्स ज्ञात कीजिए जिसका योग C++ में k के बराबर है

मान लीजिए कि हमारे पास एक 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
- योग:=योग + गिरफ्तारी [i]
- यदि योग k के समान है, तो -
  - max_length :=i + 1
  - प्रारंभ:=0
  - अंत:=मैं
- यदि योग मानचित्र में नहीं है, तो -
  - नक्शा [योग] :=मैं
- अगर (योग - के) मानचित्र में है, तो -
  - अगर max_length <(i - map[sum - k]), तो -
    - max_length :=i - map[sum - k]
    - प्रारंभ:=नक्शा [योग - के] + 1
    - अंत:=मैं
जब मैक्सिमम_लेंथ 0 न हो तो सही लौटें
मुख्य विधि से, निम्न कार्य करें -
पंक्ति:=चटाई की पंक्ति संख्या, स्तंभ:=चटाई की स्तंभ संख्या
आकार की एक सरणी अस्थायी परिभाषित करें:पंक्ति।
एक सरणी परिभाषित करें final_point ={0,0,0,0}
मैक्सएरिया:=-इन्फ
इनिशियलाइज़ लेफ्ट के लिए :=0, जब बाएँ
- तापमान को 0 से भरें
- दाएं प्रारंभ करने के लिए:=बाएं, जब दाएं
  - इनिशियलाइज़ करने के लिए:=0, जब मैं <पंक्ति, अपडेट (i 1 से बढ़ाएँ), करें -
    - अस्थायी [i]:=अस्थायी [i] + चटाई [i, दाएं]
  - योग :=sum_k(अस्थायी, ऊपर, नीचे, पंक्ति, k)
  - क्षेत्र :=(नीचे - ऊपर + 1) * (दाएं - बाएं + 1)
  - यदि योग शून्य नहीं है और अधिकतम क्षेत्रफल <क्षेत्र है, तो -
    - final_point[0] :=up, final_point[1] :=down
    - final_point[2] :=बाएँ, final_point[3]:=दाएँ
    - अधिकतम क्षेत्र :=क्षेत्र
- अगर final_point [0,0,0,0] है और mat[0,0] k नहीं है, तो
  - वापसी "कोई सब-मैट्रिक्स नहीं मिला"
शीर्ष-बाएँ बिंदु प्रदर्शित करें ( final_point[0], final_point[2])
नीचे-दाएं बिंदु प्रदर्शित करें ( final_point[1], final_point[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