Algorithmus zum Finden des Paares mit der maximalen Summe in einer in C++ geschriebenen Matrix

In diesem Artikel besprechen wir die Suche nach dem Paar mit der maximalen Summe in einer bestimmten Matrix oder einem 2D-Array. Zum Beispiel

Input : matrix[m][n] = {
   { 3, 5, 2 },
   { 2, 6, 47 },
   { 1, 64, 66 } }

Output : 130
Explanation : maximum sum is 130 from element pair 64 and 66.

Input : matrix[m][n] = {
   { 55, 22, 46 },
   { 6, 2, 1 },
   { 3, 24, 52 } }
Output : 107
Explanation : maximum sum is 130 from element pair 55 and 52.

Wege zur Lösung

Lassen Sie uns kurz die verschiedenen Vorgehensweisen erläutern, um ein gegebenes Problem problemlos zu lösen.

Brute-Force-Methode

Sie können eine Brute-Force-Methode anwenden, d. h. die Variable MAX mit der Summe der ersten beiden Elemente initialisieren, dann das Array durchlaufen und die Prüfsumme jedes Elementpaars überprüfen (falls sie signifikanter ist als MAX) und MAX ist der neue Summenwert. Dieser Vorgang wird jedoch mehr Zeit in Anspruch nehmen und die Zeitkomplexität beträgt O((m*n)2).

Effiziente Methode

Eine effiziente Methode kann übernommen werden, das heißt, die Variablen MAX1 und MAX2 werden zweimal auf 0 gesetzt und dann wird das zweidimensionale Array durchlaufen. Überprüfen Sie, ob das aktuelle Element wichtiger als MAX1 ist. Wenn ja, ersetzen Sie MAX2 durch MAX1 und MAX1 durch das vorhandene Teil. Auf diese Weise können wir die beiden größten Zahlen ermitteln. Offensichtlich ist die Summe der beiden ganzen Zahlen die größte.

Beispiel

#include <bits/stdc++.h>
using namespace std;

int main() {
   int m = 3, n = 3;
   // initialising matrix with values
   int matrix[m][n] = {
      { 55, 22, 46 },
      { 6, 2, 1 },
      { 3, 24, 52 }
   };

   // initialising MAX1 and MAX2 to keep two maximum numbers.
   int MAX1 = INT_MIN;
   int MAX2 = INT_MIN;
   int result;

   for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
      // check if the element is greater than MAX1.
         if (matrix[i][j] > MAX1) {
            MAX2 = MAX1;
            MAX1 = matrix[i][j];
         }
         // check if the current element is between MAX1 and MAX2.
         else if (matrix[i][j] > MAX2 && matrix[i][j] <= MAX1) {
            MAX2 = matrix[i][j];
         }
      }
   }
   // calculating maximum sum by adding both maximum numbers.
   result = MAX1 + MAX2;
   cout << "maximum sum in Matrix : " << result ;

   return 0;
}

Ausgabe

maximum sum in Matrix : 107

Die obige Codebeschreibung

• speichert Elemente in einem zweidimensionalen Array und initialisiert MAX1 und MAX2 mit dem Mindestwert INT.
• Durchqueren Sie die Matrix.
  • Wenn der aktuelle Teil wichtiger ist als MAX1, ersetzen Sie MAX2 durch MAX1 und MAX1 durch das aktuelle Element.
  • Wenn der aktuelle Teil schlanker als MAX1 und aussagekräftiger als MAX2 ist, dann ersetzen Sie MAX2 durch das aktuelle Element.
• Berechnen Sie das Ergebnis, indem Sie die beiden MAX1 und MAX2 addieren und drucken Sie das Ergebnis aus.

>

Fazit

In diesem Artikel haben wir darüber gesprochen, das Paar mit der maximalen Summe in einer bestimmten Matrix zu finden. Wir haben Möglichkeiten zur Lösungsfindung besprochen und auch den gleichen C++-Code besprochen. Wir können diesen Code in jeder anderen Sprache wie Java, C, Python usw. schreiben. Wir hoffen, dass dieser Artikel für Sie hilfreich war.

Das obige ist der detaillierte Inhalt vonAlgorithmus zum Finden des Paares mit der maximalen Summe in einer in C++ geschriebenen Matrix. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!