C++で書かれた行列の和が最大となるペアを見つけるアルゴリズム

この記事では、指定された行列または 2D 配列で合計が最大になるペアを見つける方法について説明します。たとえば

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.

解決策を見つける方法

与えられた問題を問題なく解決するためのさまざまな手順を簡単に説明しましょう。

ブルート フォース メソッド

ブルート フォース メソッドを適用できます。つまり、最初の 2 つの要素の合計で MAX 変数を初期化し、配列を反復処理して、次の要素の各ペアのチェックサムをチェックします。 MAX よりも重要な要素の場合) MAX は新しい合計値です。ただし、このプロセスにはさらに時間がかかり、時間計算量は O((m*n)2) になります。

効率的な方法

効率的な方法を使用できます。つまり、変数 MAX1 と MAX2 を 0 に初期化し、2 次元配列を走査して、現在の要素がMAX1 より大きいことが重要です。その場合は、MAX2 を MAX1 に置き換え、MAX1 を既存の部品に置き換えます。このようにして、最大の 2 つの数値を見つけることができます。明らかに、2 つの整数の合計が最大になります。

例

#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

上記のコードの説明

• 要素を2次元配列に格納し、MAX1とMAX2を最小値 INT 。
• マトリックスを走査します。
  • 現在の部品が MAX1 よりも重要な場合は、MAX2 を MAX1 に置き換え、MAX1 を現在の要素に置き換えます。
  • 現在のセクションが MAX1 よりも無駄がなく、MAX2 よりも意味がある場合は、MAX2 を現在の要素に置き換えます。
• 2 つの MAX1 と MAX2 を加算して結果を計算し、結果を出力します。

>

結論

この記事では、与えられた行列内で合計が最大になるペアを見つけることについて説明しました。私たちは解決策を見つける方法について話し合い、そのための C コードについても話し合いました。このコードは、Java、C、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++で書かれた行列の和が最大となるペアを見つけるアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。