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.
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
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.
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
#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; }
Wenn wir das obige Programm ausführen, generiert es die folgende Ausgabe
4 4 5 5
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!