C言語でm個の要素からなる2つの部分集合間の最大差を求める方法

この記事では、配列の中からm個の要素を選んで作った2つの部分集合の合計値の差のうち、最大となる値を求める方法を解説します。配列と数値mが与えられたとき、まず最大のm個の数値の合計を求め、そこから最小のm個の数値の合計を引くことで最大差を算出します。つまり、合計が最も大きいm個の部分集合と、合計が最も小さいm個の部分集合を見つけることがこの問題の核心です。

具体例で理解する

例1

入力：

arr = {1,2,3,4,5} ; m=3

出力：

最大差 : 6

解説： 最大の3つの数値は「3、4、5」で、その合計は12です。最小の3つの数値は「1、2、3」で、その合計は6です。したがって、最大差は12−6＝6となります。

例2

入力：

arr = {10,13,22,8,16,14} ; m=4

出力：

最大差 : 20

解説： 最大の4つの数値は「22、16、14、13」で、その合計は65です。最小の4つの数値は「8、10、13、14」で、その合計は45です。したがって、最大差は65−45＝20となります。

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

• 入力として配列arr[]と、部分集合を作るための数値mを受け取ります。
• find_diff()関数に入力配列とその長さを渡し、m個の要素からなる部分集合の合計の最大差を返します。
• まず、配列arr[]の要素を昇順にソートします。
• 次に、先頭のm個の要素と末尾のm個の要素の合計をそれぞれ求めます。これらは、配列arr[]における最小のm個の数値と最大のm個の数値に相当します。
• 最後に、両者の差を返します。
• 注意：sort(arr[], int)はソート済みの配列を返す関数であると仮定します。

この手法では、ソートにO(n log n)、合計の計算にO(m)の時間がかかるため、全体の計算量はO(n log n)となります。ソートさえ済ませれば、あとは一度のループで答えが求まる非常にシンプルなアルゴリズムです。

サンプルコード

#include<stdio.h>

// 配列の上位m個と下位m個の要素の合計差（最大差）を計算する関数
int find_diff(int arr[], int length, int m){
    // 配列をソート
    sort(arr, length);
    int maxsum = 0, minsum = 0;
    // m個の要素からなる2つの部分集合の最大差を計算
    for(int i = 0; i < m; i++){
        minsum += arr[i];
        maxsum += arr[length - i - 1];
    }
    return (maxsum - minsum);
}

// ドライバープログラム
int main(){
    int arr[] = {1, 1, 2, 3, 5, 7, 1};
    int m = 3;
    printf("%d", find_diff(arr, 7, m));
    return 0;
}

実行結果

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

12

この例では、配列{1, 1, 2, 3, 5, 7, 1}をソートすると{1, 1, 1, 2, 3, 5, 7}になります。最小の3つの合計は1+1+1＝3、最大の3つの合計は7+5+3＝15となり、その差である12が出力されます。