C++でソートされていない配列における最大ペア和を求めるアルゴリズム

この記事では、N個のソートされていない要素からなる配列 arr[] が与えられたとき、その中で最も大きい合計値を持つペア（最大ペア和）を見つける方法を解説します。

つまり、配列内の2つの要素を選んだとき、その合計が最大となる組み合わせを求めるという問題です。

問題の例

具体的な入出力例を見てみましょう。

入力 : arr[] = {7, 3, 9, 12, 1}
出力 : 21

説明：

最大の合計を持つペアは (9, 12) であり、その合計は 9 + 12 = 21 となります。

解決アプローチ

この問題に対するシンプルかつ効率的な解法は、配列内の最大値と2番目に大きい値（次点の最大値）を組み合わせたペアを作ることです。

手順は以下の通りです。

1. まず、配列の最初の要素と2番目の要素を比較し、大きい方を max、小さい方を secondMax として初期化します。
2. 次に、インデックス2から (n-1) まで配列を走査し、各要素を max および secondMax と比較します。
3. arr[i] が max より大きい場合、secondMax = max とし、max = arr[i] を代入します。
4. arr[i] が secondMax より大きい場合（ただし max とは異なる値）、secondMax = arr[i] を代入します。
5. ループが終了したら、(max + secondMax) を返します。

この手法により、配列を一度走査するだけ（O(N) の時間計算量）で答えを求められるため、ソートを行う O(N log N) の方法よりも効率的です。

C++実装例

以下は、この解法の動作を示すC++プログラムです。

#include<iostream>
using namespace std;
int findPairLargestSum(int arr[], int n){
    int max, secondMax;
    if (arr[0] > arr[1]){
        max = arr[0];
        secondMax = arr[1];
    }
    else{
        max = arr[1];
        secondMax = arr[0];
    }
    for (int i = 2; i<n; i ++){
        if (arr[i] > max){
            secondMax = max;
            max = arr[i];
        }
        else if (arr[i] > secondMax && arr[i] != max)
            secondMax = arr[i];
    }
    return (max + secondMax);
}
int main(){
    int arr[] = {12, 34, 10, 6, 40};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"最大ペア和の合計値は "<<findPairLargestSum(arr, n);
    return 0;
}

実行結果

最大ペア和の合計値は 74

この例では、配列 {12, 34, 10, 6, 40} の中で最大値 40 と2番目に大きい値 34 を組み合わせたペアが最大となり、合計は 40 + 34 = 74 となります。

まとめ

ソートされていない配列で最大ペア和を求めるには、配列をソートする必要はありません。最大値と次点の最大値を1回の走査で追跡するだけで、時間計算量 O(N)、空間計算量 O(1) で効率よく解くことができます。データ数が多い場合でも高速に動作するため、実務においても有用なアルゴリズムです。