C++で差がK未満のペアの最大合計を求める方法

はじめに

このチュートリアルでは、C++を使って「差がK未満となるペアの最大合計」を求めるプログラムについて解説します。

具体的には、整数の配列と値Kが与えられたとき、差がK未満になる要素同士をペアに組み合わせます。ただし、同じ要素を複数のペアに使うことはできません（互いに素な集合である必要があります）。この条件のもとで、選ばれたペアの要素の合計の最大値を求めるのが目的です。

解き方のポイント：動的計画法

この問題を効率的に解くには、動的計画法（DP）を活用します。まず配列を昇順にソートし、隣接する2つの要素の差がK未満であれば「それらをペアにするかどうか」をDPテーブルで判断していきます。

アルゴリズムの手順

1. 配列を昇順にソートします。
2. dp[i] を「先頭からi番目までの要素で作れる最大合計」と定義します。
3. 各iについて、次の2つのうち大きい方を採用します。
   • arr[i] をペアに使わない場合：dp[i-1]
   • arr[i] と arr[i-1] をペアにする場合：dp[i-2] + arr[i] + arr[i-1]

C++での実装例

#include <bits/stdc++.h>
using namespace std;
// 差がK未満の互いに素なペアの最大合計を返す関数
int maxSumPairWithDifferenceLessThanK(int arr[], int N, int K){
    sort(arr, arr+N);
    int dp[N];
    dp[0] = 0;
    for (int i = 1; i < N; i++) {
        dp[i] = dp[i-1];
        if (arr[i] - arr[i-1] < K) {
            if (i >= 2)
                dp[i] = max(dp[i], dp[i-2] + arr[i] + arr[i-1]);
            else
                dp[i] = max(dp[i], arr[i] + arr[i-1]);
        }
    }
    return dp[N - 1];
}
int main() {
    int arr[] = {3, 5, 10, 15, 17, 12, 9};
    int N = sizeof(arr)/sizeof(int);
    int K = 4;
    cout << maxSumPairWithDifferenceLessThanK(arr, N, K);
    return 0;
}

実行結果

62

コードの解説

入力例では、配列 {3, 5, 10, 15, 17, 12, 9} と K = 4 が与えられています。ソート後の配列は {3, 5, 9, 10, 12, 15, 17} となります。

このとき、DPによって最適に選ばれるのは (3, 5)、(10, 12)、(15, 17) の3組のペアです。それぞれの差は2、2、2といずれもK未満であり、合計は 3+5+10+12+15+17 = 62 となります。これが求める最大の合計です。

なお、(9, 10) のように差が小さいペアも存在しますが、9をペアに使うより10を12と組み合わせる方が合計が大きくなるため、DPが自動的により良い選択を行ってくれます。

計算量

ソートにO(N log N)、DPの計算にO(N)の時間がかかるため、全体の計算量はO(N log N)です。貪欲法だけでは最適解を保証できないケースもあるため、動的計画法によるアプローチが有効です。