Algoritma untuk mencari pasangan dengan jumlah maksimum dalam matriks yang ditulis dalam C++

Dalam artikel ini, kita akan membincangkan mencari pasangan dengan jumlah maksimum dalam matriks atau tatasusunan 2D tertentu. Contohnya

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.

Cara untuk mencari penyelesaian

Mari kita terangkan secara ringkas proses berbeza untuk menyelesaikan masalah yang diberikan tanpa sebarang masalah.

Kaedah brute force

Anda boleh menggunakan kaedah brute force, iaitu memulakan pembolehubah MAX dengan jumlah dua elemen pertama, kemudian lelaran melalui tatasusunan dan semak jumlah semak setiap pasangan elemen (jika ia lebih penting daripada MAX) dan MAX ialah nilai jumlah baharu. Tetapi proses ini akan mengambil lebih banyak masa, dan kerumitan masa ialah O((m*n)2).

Kaedah cekap

Kaedah yang cekap boleh diguna pakai, iaitu, mulakan dua set pembolehubah MAX1 dan MAX2 kepada 0, dan kemudian melintasi tatasusunan dua dimensi, semak sama ada elemen semasa lebih penting daripada MAX1. Jika ya, gantikan MAX2 dengan MAX1 dan MAX1 dengan bahagian sedia ada. Dengan cara ini, kita boleh mencari dua nombor terbesar Jelas sekali, jumlah dua integer adalah yang terbesar.

Contoh

#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

Penerangan kod di atas

• menyimpan elemen dalam tatasusunan dua dimensi dan memulakan MAX1 dan MAX2 dengan nilai minimum INT.
• Melintasi matriks.
  • Jika bahagian semasa lebih penting daripada MAX1, gantikan MAX2 dengan MAX1 dan MAX1 dengan elemen semasa.
  • Jika bahagian semasa lebih kurus daripada MAX1 dan lebih bermakna daripada MAX2, maka gantikan MAX2 dengan elemen semasa.
• Kira keputusan dengan menambah dua MAX1 dan MAX2 dan mencetak hasilnya.

>

Kesimpulan

Dalam artikel ini, kami membincangkan mencari pasangan dengan jumlah maksimum dalam matriks tertentu. Kami membincangkan cara untuk mencari penyelesaian dan juga membincangkan kod C++ yang sama. Kita boleh menulis kod ini dalam mana-mana bahasa lain seperti Java, C, Python, dll. Kami berharap artikel ini dapat membantu anda.

Atas ialah kandungan terperinci Algoritma untuk mencari pasangan dengan jumlah maksimum dalam matriks yang ditulis dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!