C言語で解く：k個の要素のグループと配列の残りとの最大差を求めるアルゴリズム

問題概要

サイズNの整数配列と数値kが与えられます。配列はランダムな順序の整数で構成されており、ここからk個の要素を取り出して「グループ」を作り、残りのN−k個の要素をもう一方のグループとします。求めたいのは、両グループの要素の合計値の差が最大になるようにk個の要素を選んだときの、その最大差です。

考え方

この問題のポイントは、kの大きさによって最適な選び方が変わることです。

kが小さい場合（配列サイズの半分以下）：最小のk個の要素を選べば合計が最小になり、残りのN−k個の要素は自然と大きな合計になります。したがって、最大差は「残りのN−k個の合計 − 最小k個の合計」で求められます。

kが大きい場合（配列サイズの半分より大きい）：逆に、最大のk個の要素を選べば合計が最大になり、残りのN−k個の要素は最小の合計になります。したがって、最大差は「最大k個の合計 − 残りのN−k個の合計」で求められます。

入力例1

Arr[] = { 2,5,6,1,3,2,1,4 }, k=3

出力： k要素グループと配列の残りとの最大差 → 16

解説： kが半分以下なので、最小の3つの数を選ぶのが最適です。

• 最小の3つの数：1, 1, 2 → 合計 4
• 残りのN−k＝5つの数：2, 3, 4, 5, 6 → 合計 20
• 最大差：20 − 4 = 16

入力例2

Arr[] = { 2,2,3,4,8,3,4,4,8,7 }, k=6

出力： k要素グループと配列の残りとの最大差 → 25

解説： kが半分より大きいので、最大の6つの数を選ぶのが最適です。

• 最大の6つの数：8, 8, 7, 4, 4, 4 → 合計 35
• 残りのN−k＝4つの数：2, 2, 3, 3 → 合計 10
• 最大差：35 − 10 = 25

アルゴリズムの手順

• ランダムな順序の整数配列（Arr[]）を用意し、あらかじめ昇順にソートしておきます。
• 配列のサイズを変数（N）に格納します。
• 関数 maxKDiff(int Arr[], int n, int k) を使って最大差（maxD）を計算します。
• まず配列全体の合計を計算し、arrsum に保存します。
• 続いて、forループ（i=0; i<k）を使って最小のk個の要素の合計を求めます。
• D1 には abs(配列全体の合計 − 2×最小k個の合計) を格納します。2倍するのは、配列全体の合計にもこれらの要素が含まれているためです。
• 同様に最大のk個の要素の合計を求め、D2 には abs(配列全体の合計 − 2×最大k個の合計) を格納します。
• D1 と D2 を比較し、大きい方の値を maxD として返します。

C言語による実装例

#include <stdio.h>
#include <stdlib.h>

// 昇順ソート用の比較関数
int compare(const void *a, const void *b){
    return (*(int*)a - *(int*)b);
}

// k要素グループと配列の残りとの最大差を求める関数
int maxKDiff(int arr[], int n, int k){
    // 配列全体の合計
    int arrsum = 0;
    int i;
    for(i = 0; i < n; i++)
        arrsum += arr[i];

    // 最小k個の要素の合計
    int sumk = 0;
    for(i = 0; i < k; i++)
        sumk += arr[i];

    // 最小k個を選んだ場合の差分
    int D1 = abs(arrsum - 2 * sumk);

    // 最大k個の要素の合計
    sumk = 0;
    int j = 0;
    for(i = n - 1; j < k; i--){
        sumk += arr[i];
        j++;
    }

    // 最大k個を選んだ場合の差分
    int D2 = abs(arrsum - 2 * sumk);

    // 大きい方を最大差とする
    int maxD = D1 >= D2 ? D1 : D2;

    return maxD;
}

// ドライバプログラム
int main(){
    int arr[] = { 2, 3, 2, 10, 7, 12, 8 };
    int n = 7;
    int k = 3;

    qsort(arr, n, sizeof(int), compare); // 昇順にソート

    printf("k要素のグループと配列の残りの部分との最大差 : %d", maxKDiff(arr, n, k));
    return 0;
}

実行結果

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

k要素のグループと配列の残りの部分との最大差 : 30

計算量について

このアルゴリズムでは、前処理のソートにO(N log N)、各合計の計算にO(N)かかるため、全体の時間計算量はO(N log N)となります。追加のメモリ使用量はO(1)であり、非常に効率的な解法です。「小さいk個」と「大きいk個」の両パターンの差分を比較するだけで答えが求まる点が、この手法の美しさと言えるでしょう。