C言語で正と負の整数からなる2つの部分集合間の差を最大化する方法

問題の概要

正と負の整数が混在する配列が与えられます。この課題は、配列内の要素を「正の整数の部分集合」と「負の整数の部分集合」に分けたとき、両者の差（正の部分集合の合計 − 負の部分集合の合計）が最大になる値を求めることです。

ここで重要なポイントは、負の数を引くことは、その絶対値を加えることと同じだという点です。つまり、(正の数の合計) − (負の数の合計) を最大化するには、配列内のすべての負の数を正の数に変換し、全要素の合計を求めればよいことになります。具体例を見ながら理解していきましょう。

例1

入力： Arr[] = { -2, 0, -3, 8, 10, 12, -4 }

出力： 2つの部分集合間の最大差：39

説明：

• 正の整数の部分集合 {0, 8, 10, 12} の合計は 30
• 負の整数の部分集合 {-2, -3, -4} の合計は -9
• したがって、最大差は 30 − (−9) = 39 となります。

例2

入力： Arr[] = { -5, -15, -3, -2, 10, 20, 15 }

出力： 2つの部分集合間の最大差：70

説明：

• 正の整数の部分集合 {10, 20, 15} の合計は 45
• 負の整数の部分集合 {-5, -15, -3, -2} の合計は -25
• したがって、最大差は 45 − (−25) = 70 となります。

アルゴリズムの考え方

以下のプログラムで使用しているアプローチの手順は次のとおりです。

1. 正と負の整数を含む整数配列 Arr[] を用意します。
2. 関数 subsetDifference(int arr[], int n) は、正の整数と負の整数という2つの部分集合間の差を最大化して返します。引数として配列そのものと、そのサイズ n の2つを受け取ります。
3. 配列の全要素の合計を格納するための変数 sum を 0 で初期化します。
4. forループ（i=0; i<n; i++）を使い、配列の各要素を先頭から順に走査します。
5. 現在の要素が負（<0）の場合、-1 を掛けて正の値に変換します（arr[i] = arr[i] * -1）。
6. 各要素を sum に加算していきます。
7. sum を「可能な最大の部分集合間の差」として返します。

C言語による実装例

#include <stdio.h>

int subsetDifference(int arr[], int n){
    int sum = 0;
    for (int i = 0; i < n; i++){
        if(arr[i] < 0)
            arr[i] = arr[i] * -1;  // 負の値を正に変換
        sum += arr[i];
    }
    return sum;
}

// ドライバーコード
int main(){
    int arr[] = { -1, 3, 5, 17, -32, 12 };
    int n = 6;
    printf("Maximized difference between subsets : %d", subsetDifference(arr, n));
    return 0;
}

出力結果

上記のコードを実行すると、次の出力が得られます。

Maximized difference between two subsets: 70

まとめ

この問題の鍵となるのは、「負の数を引くことは、その絶対値を加えることと等しい」という数学的な性質です。そのため、配列全体を一度走査して負の値を正に変換しながら合計を取るだけで答えが求まります。時間計算量は O(n)、追加のメモリもほとんど不要な、非常にシンプルかつ効率的なアプローチです。