使用C++編寫的矩陣中找到具有最大和的一對的演算法

在本文中，我們將討論在給定矩陣或二維陣列中尋找具有最大和的對。例如

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.

尋找解決方案的方法

讓我們簡要說明解決給定問題而不出現任何問題的不同過程。

暴力方法

可以應用暴力方法，即用前兩個元素的和初始化MAX 變量，然後遍歷數組並檢查每對元素的校驗和（如果它比MAX 更重要） MAX 為新的和值。但這個過程會花費更多的時間，時間複雜度為O((m*n)2)。

高效的方法

可以採用高效的方法，即初始化兩個-將變數MAX1 和MAX2 置為0，然後遍歷二維數組；檢查當前元素是否比MAX1 更重要。如果是，則用 MAX1 取代 MAX2，用現有零件取代 MAX1。這樣，我們就能找到兩個最大的數，顯然，兩個整數和就是最大的數。

範例

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

輸出

maximum sum in Matrix : 107

上述程式碼說明

• 在二維陣列中儲存元素，並用最小值INT 初始化MAX1 和MAX2 。
• 遍歷矩陣。
  • 如果目前部分比 MAX1 更重要，則用 MAX1 取代 MAX2，用目前元素取代 MAX1。
  • 如果目前部分是比 MAX1 更精簡，比 MAX2 更有意義，然後用目前元素取代 MAX2。
• 透過將兩個 MAX1 和 MAX2 相加計算結果並列印結果。

>

結論

在本文中，我們討論了在給定矩陣中尋找具有最大和的對。我們討論了尋找解決方案的方法，也討論了相同的 C 程式碼。我們可以用任何其他語言（例如 Java、C、Python 等）來編寫此程式碼。我們希望本文對您有所幫助。

以上是使用C++編寫的矩陣中找到具有最大和的一對的演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！