C++で|arr[i] - arr[j]| + |i-j|の最大値を効率的に求める方法

この問題では、n個の整数からなる配列が与えられます。求めるのは、|arr[i] - arr[j]| + |i-j| の最大値です。つまり、配列内の任意の2つの要素について、その値の差とインデックスの差の絶対値の合計が最大になる組み合わせを見つけるプログラムを作成します。

問題例

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

入力： array = {4, 1, 2}

出力： 4

説明：

|arr[0] - arr[1]| + |0-1| = |4-1| + |-1| = 3+1 = 4
|arr[0] - arr[2]| + |0-2| = |4-2| + |-2| = 2+2 = 4
|arr[1] - arr[2]| + |1-2| = |1-2| + |1-2| = 1+1 = 2

すべての組み合わせの中で最大値は4となり、これが答えになります。

解法1：全探索（ブルートフォース）

最もシンプルな解決策はブルートフォース（総当たり）のアプローチです。二重ループを使ってすべてのペア (i, j) を調べ、差の最大値を求めます。この方法は実装が簡単ですが、計算量はO(n²)となるため、配列が大きくなると非効率です。

解法2：絶対値の性質を活用した効率的なアプローチ

より効率的な方法は、絶対値関数の性質を利用することです。絶対値を外すと、符号の組み合わせによって式は以下の4パターンに分解できます。

arr[i] - arr[j] + i - j = (arr[i] + i) - (arr[j] + j)
arr[i] - arr[j] - i + j = (arr[i] - i) - (arr[j] - j)
-arr[i] + arr[j] + i - j = -{(arr[i] - i) - (arr[j] - j)}
-arr[i] + arr[j] - i + j = -{(arr[i] + i) - (arr[j] + j)}

よく見ると、1番目と4番目は同じ形、2番目と3番目も同じ形になっています。そこで、次のような変換が可能です。

• array1： 各要素に対して arr[i] + i を格納する
• array2： 各要素に対して arr[i] - i を格納する

すると、求める最大値は次の式で表せます。

max( (max(array1) - min(array1)), (max(array2) - min(array2)) )

この方法なら、各配列の最大値と最小値を一度ずつ求めるだけでよいため、計算量はO(n)に抑えられ、非常に効率的です。

実装例

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

#include<iostream>
using namespace std;
int maxDiff(int arr[], int n) {
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ans = max(ans, abs(arr[i] - arr[j]) + abs(i - j));
    return ans;
}
int main() {
    int array[] = { 5, 7, 1, 2 };
    int n = sizeof(array) / sizeof(array[0]);
    cout<<"|arr[i] - arr[j]| + |i-j| の最大値は "<<maxDiff(array, n);
    return 0;
}

出力結果

|arr[i] - arr[j]| + |i-j| の最大値は 7

まとめ

この記事では、配列内の2要素の値の差とインデックスの差の絶対値の和の最大値を求める問題を扱いました。単純な二重ループによるO(n²)の全探索でも解けますが、絶対値を展開して「arr[i] + i」と「arr[i] - i」の2つの配列に変換することで、O(n)の高速なアルゴリズムを実現できます。競技プログラミングやコーディング面接でも頻出のテクニックなので、ぜひ覚えておきましょう。