सी प्रोग्राम में दिए गए आकार के अधिकतम योग वर्ग उप-मैट्रिक्स को प्रिंट करें।

NxN के एक मैट्रिक्स को देखते हुए MxM का एक उप-मैट्रिक्स खोजें जहाँ M<=N और M>=1 ऐसा है कि मैट्रिक्स MxM के सभी तत्वों का योग अधिकतम है। मैट्रिक्स NxN के इनपुट में शून्य, धनात्मक और ऋणात्मक पूर्णांक मान हो सकते हैं।

उदाहरण

Input:
   {{1, 1, 1, 1, 1},
   {2, 2, 2, 2, 2},
   {3, 3, 3, 3, 3},
   {4, 4, 4, 4, 4},
   {5, 5, 5, 5, 5} }
Output:
   4 4
   5 5

उपरोक्त समस्या को एक सरल समाधान द्वारा हल किया जा सकता है जिसमें हम पूरे मैट्रिक्स एनएक्सएन ले सकते हैं, फिर सभी संभावित एमएक्सएम मैट्रिक्स का पता लगा सकते हैं और उनका योग ढूंढ सकते हैं, फिर एमएक्सएम के एक मैट्रिक्स को अधिकतम योग के साथ प्रिंट कर सकते हैं। यह तरीका आसान है लेकिन इसके लिए O(N^2.M^2) समय जटिलता की आवश्यकता होती है, इसलिए हम एक ऐसा तरीका खोजने की कोशिश करते हैं जिसमें कम समय की जटिलता हो।

एल्गोरिदम

Start
Step 1 -> Declare Function void matrix(int arr[][size], int k)
   IF k>size
      Return
   Declare int array[size][size]
   Loop For int j=0 and j<size and j++
      Set sum=0
   Loop for int i=0 and i<k and i++
      Set sum=sum + arr[i][j]
   End
   Set array[0][j]=sum
   Loop For int i=1 and i<size-k+1 and i++
      Set sum=sum+(arr[i+k-1]][j]-arr[i-1][j]
      Set arrayi][j]=sum
   End
   Set int maxsum = INT_MIN and *pos = NULL
   Loop For int i=0 and i<size-k+1 and i++)
      Set int sum = 0
      Loop For int j = 0 and j<k and j++
         Set sum += array[i][j]
      End
      If sum > maxsum
         Set maxsum = sum
         Set pos = &(arr[i][0])
      End
      Loop For int j=1 and j<size-k+1 and j++
         Set sum += (array[i][j+k-1] - array[i][j-1])
         IF sum > maxsum
            Set maxsum = sum
            Set pos = &(arr[i][j])
         End
      End
   End
   Loop For int i=0 and i<k and i++
      Loop For int j=0 and j<k and j++
         Print *(pos + i*size + j)
      End
      Print \n
   End
Step 2 -> In main()
   Declare int array[size][size] = {{1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 3, 3, 3, 3}, {4, 4, 4, 4, 4}, {5, 5, 5, 5, 5}}
   Declare int k = 2
   Call matrix(array, k)
Stop

उदाहरण

#include <bits/stdc++.h>
using namespace std;
#define size 5
void matrix(int arr[][size], int k){
   if (k > size) return;
      int array[size][size];
   for (int j=0; j<size; j++){
      int sum = 0;
      for (int i=0; i<k; i++)
         sum += arr[i][j];
         array[0][j] = sum;
      for (int i=1; i<size-k+1; i++){
         sum += (arr[i+k-1][j] - arr[i-1][j]);
         array[i][j] = sum;
      }
   }
   int maxsum = INT_MIN, *pos = NULL;
   for (int i=0; i<size-k+1; i++){
      int sum = 0;
      for (int j = 0; j<k; j++)
         sum += array[i][j];
      if (sum > maxsum){
         maxsum = sum;
         pos = &(arr[i][0]);
      }
      for (int j=1; j<size-k+1; j++){
         sum += (array[i][j+k-1] - array[i][j-1]);
         if (sum > maxsum){
            maxsum = sum;
            pos = &(arr[i][j]);
         }
      }
   }
   for (int i=0; i<k; i++){
      for (int j=0; j<k; j++)
         cout << *(pos + i*size + j) << " ";
      cout << endl;
   }
}
int main(){
   int array[size][size] = {
      {1, 1, 1, 1, 1},
      {2, 2, 2, 2, 2},
      {3, 3, 3, 3, 3},
      {4, 4, 4, 4, 4},
      {5, 5, 5, 5, 5},
   };
   int k = 2;
   matrix(array, k);
   return 0;
}

आउटपुट

यदि हम उपरोक्त प्रोग्राम चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा

4 4
5 5