C++で配列の2つの部分集合間の最大差を求める方法

はじめに

本記事では、配列の2つの部分集合間で実現できる最大の差を求めるC++プログラムについて解説します。

問題の概要

ランダムな整数が1回または2回出現する配列が与えられます。この配列を2つの部分集合に分割し、それぞれの総和の差が最大になるようにすることが課題です。ただし、同一の数値を同じ部分集合に重複して含めることはできません。

具体例

次の配列を例に考えてみます。

{ 4, 2, -3, 3, -2, -2, 8 }

1回のみ出現する正の数（4, 2, 3, 8）を部分集合1に、負の数（-3）を部分集合2に割り当てると、差は |17 − (−3)| = 20 となります。2回出現している「-2」は制約により除外されるため、この20が最大差になります。

アルゴリズムの考え方

差を最大化するためには、次の方針で要素を振り分けます。

• 重複要素の除外： 配列内に2回出現する数値は、両方とも0に置き換えて計算対象から外す。
• 正の数の集約： 1回のみ出現する正の数は、すべて部分集合1の総和に加算する。
• 負の数の集約： 1回のみ出現する負の数は、すべて部分集合2の総和に加算する。
• 差の算出： 2つの総和の差の絶対値を答えとして返す。

C++での実装例

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

// 部分集合間の最大差を求める関数
int maxDiff(int arr[], int n) {
    int SubsetSum_1 = 0, SubsetSum_2 = 0;
    for (int i = 0; i <= n - 1; i++) {
        bool isSingleOccurance = true;
        for (int j = i + 1; j <= n - 1; j++) {
            if (arr[i] == arr[j]) {
                isSingleOccurance = false;
                arr[i] = arr[j] = 0;
                break;
            }
        }
        if (isSingleOccurance) {
            if (arr[i] > 0)
                SubsetSum_1 += arr[i];
            else
                SubsetSum_2 += arr[i];
        }
    }
    return abs(SubsetSum_1 - SubsetSum_2);
}

int main() {
    int arr[] = { 4, 2, -3, 3, -2, -2, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Difference = " << maxDiff(arr, n);
    return 0;
}

実行結果

Maximum Difference = 20

コードの解説

maxDiff関数では、外側のループで各要素を取り上げ、内側のループでその後ろに同じ値の要素が存在するかどうかを調べます。重複が見つかった場合は、両方の要素を0に設定して以降の計算から除外します。

重複しない要素については、正の値ならSubsetSum_1へ、負の値ならSubsetSum_2へ加算していきます。最後にabs()で2つの総和の差の絶対値を返すことで、条件を満たす最大差が求まります。

計算量について

この実装は二重ループを使用しているため、時間計算量はO(n²)です。std::unordered_mapなどを使って各要素の出現回数を事前にカウントしておけば、O(n)まで高速化することも可能です。入力サイズが大きくなる場合は、この改善を検討するとよいでしょう。