C++で同じ合計になるペアの最大数を求める方法

整数の配列が与えられたとき、配列内の2つの要素からなるペアを足し合わせた結果が同じ合計となるペアのうち、最も多く存在するケースのペア数を求めるのがこの問題の目的です。同じ合計を生成するペアが最大でいくつ現れるかを計算します。

入力例

Arr[]= { 1,2,3,4,2 }

出力例

同じ合計を持つペアの最大数 : 3

説明 − 各ペアの合計は以下のようになります −

{1,2}, {1,2} 合計:3
{1,3},{2,2} 合計:4
{1,4},{2,3},{3,2} 合計:5
{2,4} 合計:6
{3,4} 合計:7
同じ合計を持つペアの最大数は3です(合計 = 5 の場合)

入力例

Arr[]= { 5,3,6,1 }

出力例

同じ合計を持つペアの最大数 : 1

説明 − 各ペアの合計は以下のようになります −

{5,3} 合計:8
{5,6} 合計:11
{5,1} 合計:6
{3,6} 合計:9
{3,1} 合計:4
{6,1} 合計:7
同じ合計を持つペアの最大数は1です。

プログラムで使用するアプローチ

• 整数配列 Arr[] を使用して、対象となる整数を格納します。

• 整数型の変数 'size' には、配列の長さを格納します。

• 関数 countEqualSum(int arr[], int n) は、配列とそのサイズを引数として受け取り、同じ合計を生成するペアの最大数を返します。

• まず、一意な合計値ごとの出現回数を記録するための 'sum' 配列を用意します。

• すべてのペアの合計を計算し、対応する sum 配列のインデックスのカウントを1ずつ増やしていきます。

• sum 配列の各インデックスは「あるペアの合計値」を表し、その値は同じ合計を持つペアの出現回数となります。

• sum 配列内を走査して最大値を検索し、maxC に格納します。

• 最後に maxC を結果として返します。

このアルゴリズムの計算量は、すべてのペアを列挙するため O(n²) となります。配列の要素が小さい範囲に収まる場合、合計値を配列のインデックスとして直接管理できるため、非常にシンプルかつ効率的に実装できます。

コード例

#include <bits/stdc++.h>
using namespace std;
// 同じ合計を持つペアの最大数を返す関数
int countEqualSum(int arr[], int n){
    int sum[20]={0};
    int maxC = 0;
    // すべてのペアの合計の出現回数を記録
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++){
            sum[ arr[i]+arr[j] ]++;
        }
        for(int i=0;i<20;i++)
            if(sum[i]>maxC)
                maxC=sum[i];
    return maxC;
}
int main(){
    int Arr[] = { 1,2,3,4,2 };
    int size = 5;
    cout <<"同じ合計を生成するペアの最大数 : "
    << countEqualSum(Arr, size);
    return 0;
}

出力

同じ合計を生成するペアの最大数 : 3