C++で合計が最大となるペアの個数を求めるアルゴリズム

問題の概要

配列が与えられたとき、「合計が最大となるペア」がいくつ存在するかを求める問題です。まずは具体例で確認しましょう。

入力

arr = [3, 4, 5, 2, 1, 2, 3, 4, 1, 5]

出力

1

この配列でペアの合計が最大になるのは 5 + 5 = 10 です。合計が 10 になるペアは (5, 5) の 1 組のみのため、答えは 1 となります。

アルゴリズム

考え方はシンプルで、以下の手順に従います。

1. 配列を用意します。
2. 最大合計(maxSum)を INT_MIN で初期化します。
3. 二重ループですべてのペアを調べ、ペアの合計の最大値を求めます。
4. ペアの個数を数えるためのカウンタを 0 で初期化します。
5. もう一度二重ループで配列を走査し、ペアの合計が最大合計と一致したらカウンタをインクリメントします。
6. カウンタの値(ペアの個数)を返します。

C++での実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;

// 合計が最大となるペアの個数を返す関数
int getMaxSumPairsCount(int a[], int n) {
    int maxSum = INT_MIN;

    // ステップ1: すべてのペアの中から最大の合計を求める
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            maxSum = max(maxSum, a[i] + a[j]);
        }
    }

    int count = 0;

    // ステップ2: 最大の合計になるペアの個数を数える
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] + a[j] == maxSum) {
                count++;
            }
        }
    }

    return count;
}

int main() {
    int arr[] = { 3, 4, 5, 2, 1, 2, 3, 4, 1, 5 };
    int n = 10;
    cout << getMaxSumPairsCount(arr, n) << endl;
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、次の出力が得られます。

1

計算量について

この実装では二重ループですべてのペアを調べるため、時間計算量は O(n²)、空間計算量は O(1) になります。

より効率化したい場合は、配列を降順にソートして最大値と2番目に大きい値の組み合わせを確認する方法(O(n log n))や、1回の走査で上位2つの値を追跡しながらペアを数える方法(O(n))も検討できます。