Heim > Backend-Entwicklung > C++ > Drucken Sie die maximale Summenquadrat-Submatrix einer bestimmten Größe im C-Programm

Drucken Sie die maximale Summenquadrat-Submatrix einer bestimmten Größe im C-Programm

WBOY
Freigeben: 2023-09-07 13:53:04
nach vorne
1330 Leute haben es durchsucht

Suchen Sie bei einer gegebenen NxN-Matrix eine MxM-Untermatrix mit M=1, so dass die Summe aller Elemente der Matrix MxM maximal ist. Die Eingabe in die Matrix NxN kann Null, positive ganzzahlige und negative ganzzahlige Werte enthalten.

Drucken Sie die maximale Summenquadrat-Submatrix einer bestimmten Größe im C-Programm

Beispiel

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
Nach dem Login kopieren

Das obige Problem kann mit einer einfachen Lösung gelöst werden: Wir können die gesamte Matrix NxN nehmen und dann alle möglichen MxM-Matrizen finden, ihre Summe finden und dann die mit der MxM-Matrix mit der maximalen Summe drucken. Diese Methode ist einfach, erfordert jedoch eine Zeitkomplexität von O(N^2.M^2), daher versuchen wir, eine Methode mit weniger Zeitkomplexität zu finden.

Algorithmus

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 </p><p>
   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
Nach dem Login kopieren

Beispiel

#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;
}
Nach dem Login kopieren

Ausgabe

Wenn wir das obige Programm ausführen, generiert es die folgende Ausgabe

4 4
5 5
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonDrucken Sie die maximale Summenquadrat-Submatrix einer bestimmten Größe im C-Programm. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage