【C++】最大重み差を計算するプログラムの実装方法

この記事では、配列 arr[] と数値 M が与えられたときに、C++ で最大重み差を計算するプログラムの作成方法について解説します。

問題の概要

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

具体例を使って問題を確認しましょう。

• 入力: arr[] = {3, 1, 6, 9, 4}、M = 3
• 出力: 15

解説

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

|19 − 4| = 15

解決アプローチ

この問題の鍵となるのは、「最大の差が生じるのは、必ず M 個の大きい要素 を選んだ場合か M 個の小さい要素 を選んだ場合のどちらかである」という性質です。

そのため、両方のパターンを計算し、それぞれの絶対差を比較することで最終的な答えを求められます。また、M 個の最大値・最小値を効率よく取り出すために、まず配列全体をソートしてから、下位 M 要素と上位 M 要素に対して計算を行うのが効果的です。

アルゴリズムの手順

1. 配列を昇順にソートする。
2. 配列全体の合計を求めると同時に、下位 M 要素の合計（sumMin）と上位 M 要素の合計（sumMax）を算出する。
3. |sumMax −（総和 − sumMax）| と |sumMin −（総和 − sumMin）| を比較し、大きい方を結果として返す。

サンプルコード

#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

計算量について

• 時間計算量: O(N log N) ― 配列のソートが支配的となります。
• 空間計算量: O(1) ― 追加の配列などは使用せず、定数個の変数のみで処理できます。

このように、ソートを活用することでシンプルなループ処理だけで最大重み差を効率的に求めることができます。競技プログラミングでも頻出する考え方なので、ぜひマスターしておきましょう。