Algorithme pour trouver la paire de somme maximale dans une matrice écrite en C++

Dans cet article, nous discuterons de la recherche de la paire avec une somme maximale dans une matrice ou un tableau 2D donné. Par exemple

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.

Façons de trouver une solution

Expliquons brièvement les différents processus pour résoudre un problème donné sans aucun problème.

Méthode de force brute

Vous pouvez appliquer une méthode de force brute, c'est-à-dire initialiser la variable MAX avec la somme des deux premiers éléments, puis parcourir le tableau et vérifier la somme de contrôle de chaque paire d'éléments (si elle est plus significative que MAX) et MAX est la nouvelle valeur de la somme. Mais ce processus prendra plus de temps et la complexité temporelle est O((m*n)2).

Méthode efficace

Une méthode efficace peut être adoptée, c'est-à-dire initialiser deux variables MAX1 et MAX2 à 0, puis parcourir le tableau bidimensionnel ; vérifier si l'élément actuel est plus important que MAX1. Si tel est le cas, remplacez MAX2 par MAX1 et MAX1 par la pièce existante. De cette façon, nous pouvons trouver les deux plus grands nombres. Évidemment, la somme des deux entiers est la plus grande.

Exemple

#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;
}

Output

maximum sum in Matrix : 107

La description du code ci-dessus

• stocke les éléments dans un tableau bidimensionnel et initialise MAX1 et MAX2 avec la valeur minimale INT.
• Parcourez la matrice.
  • Si la partie actuelle est plus importante que MAX1, remplacez MAX2 par MAX1 et MAX1 par l'élément actuel.
  • Si la partie actuelle est plus simple que MAX1 et plus significative que MAX2, remplacez MAX2 par l'élément actuel.
• Calculez le résultat en additionnant les deux MAX1 et MAX2 et imprimez le résultat.

>

Conclusion

Dans cet article, nous avons discuté de la recherche de la paire avec une somme maximale dans une matrice donnée. Nous avons discuté des moyens de trouver des solutions et avons également discuté du même code C++. Nous pouvons écrire ce code dans n'importe quel autre langage comme Java, C, Python, etc. Nous espérons que cet article vous a été utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!