C++で配列の最大重み差（Maximum Weight Difference）を求める方法

この記事では、配列 arr[] と整数 M が与えられたとき、C++ を使って最大重み差（Maximum Weight Difference）を計算する方法を解説します。

問題の概要

配列の中から M 個の要素を選び、選んだ要素の合計と残りの要素の合計との絶対差が最大になるようにします。

具体例で確認してみましょう。

入力例

arr[] = {3, 1, 6, 9, 4}　M = 3

出力例

15

説明

この例では 4、6、9 を選びます。その合計は 19 です。残りの要素（3 と 1）の合計は 4 なので、絶対差は次のように計算できます。

|19 − 4| = 15

解法アプローチ

最も単純な方法は、配列のすべての部分列を列挙し、それぞれについて選んだ要素の合計と残りの要素の合計の差を計算して、その最大値を返すことです。しかし、この方法は部分列の数だけ繰り返し処理が必要になるため、計算量が膨大になり実用的ではありません。

そこで、次の重要な性質を利用すると効率的に解けます。
「M 個の最大要素」または「M 個の最小要素」を選んだときに、重み差が最大になる。

つまり、以下の 2 パターンについて差を計算すれば十分です。

• 大きい方から M 個の要素を選んだ場合の合計差
• 小さい方から M 個の要素を選んだ場合の合計差

そして、両者のうち大きい方を答えとして返します。

アルゴリズム

初期化：

maxabsDiff, sumMin, sumMax, arrSum

ステップ 1：

配列をソートする。

ステップ 2：

配列全体の合計 arrSum を計算しながら、
先頭から M 個の要素の合計 sumMin と、
末尾から M 個の要素の合計 sumMax を求める。

ステップ 3：

|sumMax − (arrSum − sumMax)| と
|sumMin − (arrSum − sumMin)| を比較し、
大きい方を maxabsDiff とする。

ステップ 4：

maxabsDiff を返す。

実装例

上記の解法を実装した C++ プログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
int maxWeightDifference(int arr[], int N, int M){
    int maxabsDiff = -1000;
    sort(arr, arr + N);
    int sumMin = 0, sumMax = 0, arrSum = 0;
    for(int i = 0; i < N; i++){
        arrSum += arr[i];
        if(i < M)
            sumMin += arr[i];
        if(i >= (N-M))
            sumMax += arr[i];
    }
    maxabsDiff = max(abs(sumMax - (arrSum - sumMax)), abs(sumMin - (arrSum - sumMin)));
    return maxabsDiff;
}
int main(){
    int arr[] = {3, 1, 6, 9, 4} ;
    int M = 3;
    int N = sizeof(arr)/sizeof(arr[0]);
    cout<<"The maximum weight difference is "<<maxWeightDifference(arr,N, M);
    return 0;
}

出力

The maximum weight difference is 15

まとめ

この問題は、全探索を行わずに「最大 M 個」と「最小 M 個」の 2 通りだけを評価することで、O(N log N) の計算量（ソートのコストが支配的）で効率的に解くことができます。配列の合計を一度求めておき、部分集合の合計との差を比較するシンプルな発想がポイントです。