【C++】2つの配列から最大の合計を持つペアの合計を求める方法

問題概要

この記事では、正の整数かつ互いに異なる要素からなる2つの配列が与えられ、2つの配列から選んだペアの中で最大の合計を求めるという問題を扱います。

つまり、それぞれの配列から1つずつ要素を選んで作られるペアの中から、合計が最大になる組み合わせを見つけます。

具体例で問題を確認しよう

入力 : arr1[] = {3, 7, 5}, arr2[] = {8, 2, 4}
出力 : 15

説明 −

最大ペアは (7, 8) → 7 + 8 = 15

解き方のアプローチ

アプローチ1: ネストしたループによる全探索

最もシンプルな方法は、ループを使ってすべてのペアの合計を調べることです。ネストしたループで全ペアの合計を計算し、その中で最大のものを返します。ただし、この方法の時間計算量は O(n1 × n2) となり、配列のサイズが大きくなると処理が遅くなるという欠点があります。

アプローチ2: 各配列の最大要素を探す（効率的な方法）

より効率的なのが、各配列の最大要素を見つけて、その2つを足し合わせる方法です。「最大の合計を持つペア」は必ず「各配列の最大要素」の組み合わせになるため、ネストしたループを使わなくても、各配列に対して単純なループを1回ずつ回すだけで答えが求まります。時間計算量は O(n1 + n2) に抑えられます。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;
int findMaxPairSum(int arr1[], int n1, int arr2[], int n2) {
   int max1 = -1;
   int max2 = -1;
   for (int i = 0; i < n1; i++) {
      if (arr1[i] > max1)
         max1 = arr1[i];
   }
   for (int i = 0; i < n2; i++) {
      if (arr2[i] > max2)
         max2 = arr2[i];
   }
   return (max1 + max2);
}
int main() {
   int arr1[] = { 3, 7, 5 };
   int arr2[] = { 8, 2, 4 };
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   int n2 = sizeof(arr2) / sizeof(arr2[0]);
   cout<<"2つの配列から選べる最大のペアの合計 "<<findMaxPairSum(arr1, n1, arr2, n2);
   return 0;
}

出力

2つの配列から選べる最大のペアの合計 15

アプローチ3: ソートを利用する方法

もう一つのアプローチとして、配列をソートしてしまう方法もあります。昇順にソートすれば最大値は配列の末尾に来るため、両配列の末尾要素を足し合わせるだけで最大ペアの合計が求まります。ただし、ソートには O(n log n) のコストがかかるため、単に最大値を求めるだけであればアプローチ2の方が高速です。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
int findMaxPairSum(int arr1[], int n1, int arr2[], int n2) {
   sort(arr1, arr1 + n1);
   sort(arr2, arr2 + n2);
   return (arr1[n1 - 1] + arr2[n2 - 1]);
}
int main() {
   int arr1[] = { 3, 7, 5 };
   int arr2[] = { 8, 2, 4 };
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   int n2 = sizeof(arr2) / sizeof(arr2[0]);
   cout<<"2つの配列から選べる最大のペアの合計 "<<findMaxPairSum(arr1, n1, arr2, n2);
   return 0;
}

出力

2つの配列から選べる最大のペアの合計 15

まとめ

「2つの配列から最大の合計を持つペアを求める」問題は、各配列の最大要素を1回の走査で見つけて足し合わせることで、O(n1 + n2) の効率的に解くことができます。全探索 O(n1 × n2) やソートを利用する方法 O(n log n) も正しい解ですが、要素数が多いデータを扱う場合は、最大値を直接求めるアプローチ2が最もおすすめです。