【C++】|arr[0]−arr[1]|＋|arr[1]−arr[2]|＋…＋|arr[n−2]−arr[n−1]|の最大値を求める方法

この問題では、1からnまでの範囲に含まれるn個の整数で構成された配列が与えられます。求めるのは、隣接する要素同士の絶対差の合計 |arr[0] − arr[1]| ＋ |arr[1] − arr[2]| ＋ … ＋ |arr[n−2] − arr[n−1]| を最大化するような並べ方における、その最大値です。

問題の例

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

• 入力： array = {1, 2, 3}
• 出力： 3

説明：

最大の合計は
|1−3| ＋ |2−1| = 3

解き方のアプローチ

最も単純な方法は、配列のすべての順列を生成し、それぞれについて絶対差の合計を計算して最大値を探すことです。しかし、順列の数はn!で爆発的に増えるため、非効率です。

そこで有効なのが、各nの値に対して最大値を求め、そのパターンから一般式を導出するという方法です。要素を大小交互に並べる（ジグザグに配置する）ことで、隣接要素間の差を最大化できることが知られています。

実際に小さなnで計算してみると、次のようになります。

n = 1 のときの最大合計 = 0
n = 2 のときの最大合計 = 1
n = 3 のときの最大合計 = 3
n = 4 のときの最大合計 = 7
n = 5 のときの最大合計 = 11
→ 最大値は 0, 1, 3, 7, 11… と続く

この数列から導かれる一般式は次の通りです。

((n × n / 2) − 1)

※ n = 1 の場合は特別扱いとして 0 を返します。n ≥ 2 であれば、この式（整数除算）が正しく機能します。

C++での実装例

上記の解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;

int maxAbsVal(int n) {
    if (n == 1)
        return 0;
    return ((n * n / 2) - 1);
}

int main() {
    int n = 4;
    cout << "The maximum sum of absolute difference is " << maxAbsVal(n);
    return 0;
}

実行結果

The maximum sum of absolute difference is 7

まとめ

全順列を試す力まかせの手法ではO(n!)の計算量が必要ですが、一般式 (n² / 2) − 1 を使えばO(1)で答えを求められます。配列の要素を高低交互に並べることで絶対差の合計が最大化されるという性質を利用した、非常に効率的な解法です。