特定の差を持つペアの最大合計を求めるC++プログラム

問題の概要

この問題では、n個の整数からなる配列 arr[] と数値 d が与えられます。求めるのは、要素間の差が d 未満となるペアの中で、その合計が最大になる組み合わせを見つけることです。

問題の詳細： ペアを構成する2つの要素の差が d より小さくなるようにペアを作成し、それらのペアの要素の合計が最大となるようにします。

入出力例

入力：

arr[] = {5, 9, 11, 7, 2, 12, 3}, d = 5

出力：

47

説明：

最大合計に寄与するペア: (3, 5), (7, 9), (11, 12)
合計 = 3 + 5 + 7 + 9 + 11 + 12 = 47

解法アプローチ

最も単純な方法は、配列内のすべての有効なペアを作成し、それぞれの合計を計算して最大値を返すことです。しかし、この総当たり的な方法は非効率であり、計算量が大きくなってしまいます。

そこで効率的な解法として動的計画法（DP）を用います。まず配列を昇順にソートし、隣接する要素同士がペアを構成できるかを順に確認していきます。各時点での「その要素までのペア合計の最大値」をDPテーブルに記録し、現在の要素と直前の要素でペアが作れる場合は、「ペアを構成した場合の合計」と「構成しない場合の合計」を比較して、より大きい方を採用します。これにより、全体の最適解を効率的に求められます。

アルゴリズム

1. DP配列 DP[n] を初期化します。
2. DP[0] = 0 と設定します（最初の要素の前にペアは存在しないため）。
3. i を 1 から n-1 までループさせます。
   • 現在の要素と直前の要素でペアが可能か確認します。すなわち arr[i] - arr[i-1] < d かどうかです。
   • ペアが可能な場合、DP[i-2] + arr[i-1] + arr[i]（このペアを採用した場合の合計）と DP[i-1]（採用しない場合の合計）を比較し、大きい方を DP[i] とします。
   • i = 1 の場合は例外的な処理が必要です。DP[i-2] が存在しないため、最初のペアの合計 arr[i-1] + arr[i] と比較します。
4. 最後に DP[n-1] を結果として返します。

C++実装例

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

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

int CalcmaxPairSum(int arr[], int n, int d) {
    sort(arr, arr+n);
    int maxSumDP[n];
    maxSumDP[0] = 0;
    for (int i = 1; i < n; i++) {
        maxSumDP[i] = maxSumDP[i-1];
        if (arr[i] - arr[i-1] < d) {
            if (i >= 2) {
                if (maxSumDP[i] < (maxSumDP[i-2] + arr[i-1] + arr[i]))
                    maxSumDP[i] = maxSumDP[i-2] + arr[i-1] + arr[i];
            } else {
                if (maxSumDP[i] < (arr[i-1] + arr[i]))
                    maxSumDP[i] = arr[i-1] + arr[i];
            }
        }
    }
    return maxSumDP[n-1];
}

int main() {
    int arr[] = {5, 9, 11, 7, 2, 12, 3};
    int n = 7, d = 5;
    cout<<"特定の差を持つペアの最大合計は "<<CalcmaxPairSum(arr, n, d);
    return 0;
}

実行結果

特定の差を持つペアの最大合計は 47

まとめ

この解法では、配列のソートに O(n log n)、DPによる計算に O(n) の時間計算量が必要となります。総当たり法の O(n²) と比較して大幅に効率化されており、動的計画法を用いることで部分問題の最適解から全体の最適解を確実に導き出せる点がポイントです。差の制約付きペア選択問題は、貪欲法やDPの学習教材としても非常に有用な典型問題といえます。