C++で解く！配列の順列における絶対差の最大和を求めるアルゴリズム

この記事では、与えられた配列の要素を並べ替えたときに、隣接する要素同士の絶対差の合計が最大になる値を求めるプログラムをC++で実装する方法を解説します。

問題の概要

与えられた配列の要素からすべての順列を生成し、各順列について隣接要素間の絶対差の合計を計算します。そして、それらの合計の中で最大となる値を答えとして返します。なお、ここでは配列を環状とみなし、末尾の要素と先頭の要素の差も合計に含めます。

具体例を使って問題を理解しましょう。

入力

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

出力

22

説明

配列 {9, 1, 6, 3} の順列の一つ {9, 3, 6, 1} を見てみましょう。

sum = |9-3| + |3-6| + |6-1| + |1-9| = 6 + 3 + 5 + 8 = 22

別の順列 {9, 1, 3, 6} では次のようになります。

sum = |9-1| + |1-3| + |3-6| + |6-9| = 8 + 2 + 3 + 3 = 16

考えられるすべての順列を調べると、最大値は 22 であることがわかります。

解法のアプローチ

すべての順列を総当たりで調べることも可能ですが、要素数が n の場合に n! 通りの並び方をチェックする必要があり、n が大きくなると現実的な時間では処理できません。

そこで、絶対差の合計を最大化するコツに着目します。それは「最小値と最大値を交互に並べる」ことです。こうすることで |最小値 − 最大値| という大きな差を何度も作り出せるため、合計を最大化できます。

アルゴリズム

ステップ1 − 配列を昇順にソートします。

ステップ2 − ソート済み配列の小さい側の要素と大きい側の要素を交互に並べた新しい配列を作成します。

ステップ3 − 新しい配列の隣接要素間の絶対差をすべて合計し、さらに末尾と先頭をつなぐ差も加算します。

ステップ4 − 計算された最大合計（maxSum）を返します。

C++での実装例

上記の解法を実装したプログラムがこちらです。

#include <bits/stdc++.h>
using namespace std;

int calcMaxSumAbsDiff(int arr[], int N){
    int maxSumArray[N];
    int j = 0, maxSum = 0;
    sort(arr, arr + N);
    // 小さい要素と大きい要素を交互に配置
    for (int i = 0; i < (N/2); ++i){
        maxSumArray[j] = arr[i];
        maxSumArray[j+1] = arr[N - i - 1];
        j += 2;
    }
    // 要素数が奇数の場合は中央の要素を追加
    if (N % 2 != 0)
        maxSumArray[j] = arr[N/2];
    // 隣接要素間の絶対差を合計
    for (int i = 0; i < N - 1; i++){
        maxSum += abs(maxSumArray[i] - maxSumArray[i + 1]);
    }
    // 環状として扱うため、末尾と先頭の差も加算
    maxSum += abs(maxSumArray[N - 1] - maxSumArray[0]);
    return maxSum;
}

int main(){
    int arr[] = {9, 1, 6, 3};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout<<"任意の順列における絶対差の最大和: "<<calcMaxSumAbsDiff(arr, N);
}

実行結果

任意の順列における絶対差の最大和: 22

まとめ

この問題は、配列をソートして大小の要素を交互に並べることで、全順列を試すことなく O(N log N) の計算量で効率的に解くことができます。ポイントは、隣接要素の差を最大化するために「最小値と最大値を交互に配置する」という発想です。ぜひ自分のプロジェクトでも活用してみてください。