C++で隣接する要素の差の最大合計を求める方法

本記事では、数値 N が与えられたとき、C++ を用いて「隣接する要素の差の絶対値の合計」が最大となる値（maxSum）を求める方法を解説します。

問題の概要

1 から N までの整数で作られるすべての順列を対象に、隣接する要素同士の差の絶対値を合計し、その最大値を求めるのが目的です。

入力例

N = 4

出力例

7

解説

N = 4 の場合、考えられるすべての順列（4! = 24 通り）について、隣接要素の差の絶対値の合計を計算すると以下のようになります。

{1, 2, 3, 4} → 1 + 1 + 1 = 3
{1, 2, 4, 3} → 1 + 2 + 1 = 4
{1, 3, 2, 4} → 2 + 1 + 2 = 5
{1, 3, 4, 2} → 2 + 1 + 2 = 5
{1, 4, 2, 3} → 3 + 2 + 1 = 6
{1, 4, 3, 2} → 3 + 1 + 1 = 5
{2, 1, 3, 4} → 1 + 2 + 1 = 4
{2, 1, 4, 3} → 1 + 3 + 1 = 5
{2, 3, 1, 4} → 1 + 2 + 3 = 6
{2, 3, 4, 1} → 1 + 1 + 3 = 5
{2, 4, 1, 3} → 2 + 3 + 2 = 7　★最大
{2, 4, 3, 1} → 2 + 1 + 2 = 5
{3, 1, 2, 4} → 2 + 1 + 2 = 5
{3, 1, 4, 2} → 2 + 3 + 2 = 7　★最大
{3, 2, 1, 4} → 1 + 1 + 3 = 5
{3, 2, 4, 1} → 1 + 2 + 3 = 6
{3, 4, 1, 2} → 1 + 3 + 1 = 5
{3, 4, 2, 1} → 1 + 2 + 1 = 4
{4, 1, 2, 3} → 3 + 1 + 1 = 5
{4, 1, 3, 2} → 3 + 2 + 1 = 6
{4, 2, 1, 3} → 2 + 1 + 2 = 5
{4, 2, 3, 1} → 2 + 1 + 2 = 5
{4, 3, 1, 2} → 1 + 2 + 1 = 4
{4, 3, 2, 1} → 1 + 1 + 1 = 3

最大値は 7 であり、これは {2, 4, 1, 3} のように大きな数と小さな数を交互に並べることで達成されます。この「大小を交互に配置する」という発想が、隣接差の合計を最大化する鍵となります。

解法のアプローチ：一般式を導き出す

全順列を生成して調べる力任せの方法では、計算量が O(N!) となり、N が少し大きくなるだけで現実的な時間内に処理できません。そこで、いくつかの N に対する maxSum の値を観察し、その規則性から一般式（閉形式）を導き出す方針を取ります。

N = 2 のとき maxSum = 1
N = 3 のとき maxSum = 3
N = 4 のとき maxSum = 7
N = 5 のとき maxSum = 11
N = 6 のとき maxSum = 17
N = 7 のとき maxSum = 23
N = 8 のとき maxSum = 31

この数列は、「1 から N−1 までの総和 S(N) = N(N−1)/2」と「未知の関数 F(N)」の和として表せそうだと推測できます。

maxSum(N) = S(N) + F(N)　※S(N) = N(N−1)/2

既知の値から F(N) を逆算してみましょう。

F(2) = 0
F(3) = 0
F(4) = 1
F(5) = 1
F(6) = 2
F(7) = 2
F(8) = 3

結果を整理すると、F(N) は N が 2 増えるごとに 1 ずつ増加し、N = 2, 3 のときは 0 になっていることがわかります。したがって、F(N) は「N を 2 で割った商（整数部分）から 1 を引いた値」、すなわち F(N) = ⌊N/2⌋ − 1 と表せます。

この関係を maxSum の式に代入して変形すると、次のようなシンプルな一般式が得られます。

maxSum = N(N−1)/2 + N/2 − 1
       = (N(N−1) + N − 2) / 2
       = (N² − N + N − 2) / 2
       = (N² − 2) / 2

この公式を使えば、任意の N に対して maxSum を定数時間 O(1) で計算できます。

C++ による実装例

上記の公式を実装したサンプルプログラムがこちらです。

#include <iostream>
using namespace std;

int calcMaxSumofDiff(int N){
    int maxSum = 0;
    maxSum = ((N * N) - 2) / 2;
    return maxSum;
}

int main(){
    int N = 13;
    cout << "The maximum sum of difference of adjacent elements is " << calcMaxSumofDiff(N);
    return 0;
}

実行結果

The maximum sum of difference of adjacent elements is 83

N = 13 のとき、(13² − 2) / 2 = 167 / 2 = 83（整数除算のため小数点以下は切り捨て）となり、公式どおりの結果が出力されていることが確認できます。

まとめ

隣接要素の差の最大合計を求める問題では、全順列を列全順列を列挙しなくても、小さい N での値を観察して規則性を見つけ、maxSum = (N² − 2) / 2 という一般式を導出することで高速に解答できます。「具体例からパターンを見抜き、閉形式に落とし込む」という手法は競技プログラミングなどでも頻出のテクニックなので、ぜひ身につけておきましょう。