C言語で「値とインデックスの合計」の最大絶対差を求める方法

問題の概要

整数の配列が与えられたとき、「値とインデックスの合計」の最大絶対差を計算するのがこの記事の課題です。具体的には、配列内の各インデックスのペア (i, j) について |Arr[i] − Arr[j]| + |i − j| を計算し、その最大値を求めます。ここで |A| は A の絶対値を表します。配列の要素数が 4 であれば、インデックスは 0, 1, 2, 3 となり、考えられるユニークなペアは (0,0)、(1,1)、(2,2)、(3,3)、(0,1)、(0,2)、(0,3)、(1,2)、(1,3)、(2,3) の 10 個です。

入力例 1

入力 − Arr[] = { 1, 2, 4, 5 }
出力 − 値とインデックスの合計の最大絶対差: 7

説明 − 各インデックスペアと |A[i] − A[j]| + |i − j| の値は以下の通りです。

1. (0,0), (1,1), (2,2), (3,3) --------- 各ペアの |i-j| は 0
2. (0,1) ---------- |1-2| + |0-1| = 1+1 = 2
3. (0,2) ---------- |1-4| + |0-2| = 3+2 = 5
4. (0,3) ---------- |1-5| + |0-3| = 4+3 = 7
5. (1,2) ---------- |2-4| + |1-2| = 2+1 = 3
6. (1,3) ---------- |2-5| + |1-3| = 3+2 = 5
7. (2,3) ---------- |4-5| + |2-3| = 1+1 = 2
これらの合計の最大値は 7 です。

入力例 2

入力 − Arr[] = { 10, 20, 21 }
出力 − 値とインデックスの合計の最大絶対差: 13

説明 − 各インデックスペアと |A[i] − A[j]| + |i − j| の値は以下の通りです。

1. (0,0), (1,1), (2,2) --------- 各ペアの |i-j| は 0
2. (0,1) ---------- |10-20| + |0-1| = 10+1 = 11
3. (0,2) ---------- |10-21| + |0-2| = 11+2 = 13
4. (1,2) ---------- |20-21| + |1-2| = 1+1 = 2
これらの合計の最大値は 13 です。

プログラムのアプローチ

• 数値を格納した整数配列 Arr[] を受け取ります。

• 関数 maxabsDiff(int arr[], int n) が、値とインデックスの合計の最大絶対差を計算します。

• 変数 result を 0 で初期化します(絶対値は必ず 0 以上になるため)。

• 外側の for ループで、配列を先頭から順に走査します。

• 内側のネストされた for ループで残りの要素を走査し、要素の値とインデックス i, j の絶対差の合計 (abs(arr[i] - arr[j]) + abs(i - j)) を計算して、変数 absDiff に格納します。

• 新しく計算した合計がこれまでの最大値より大きければ、result に格納します。

• 配列全体を走査し終えたら、result を返します。

この方法はすべてのペアを総当たりで調べるため、計算量は O(n²) になります。要素数が少ない配列であれば十分実用的です。

サンプルコード(C)

#include <stdio.h>
#include <stdlib.h>

// 最大絶対差を返す関数
int maxabsDiff(int arr[], int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int absDiff = abs(arr[i] - arr[j]) + abs(i - j);
            if (absDiff > result)
                result = absDiff;
        }
    }
    return result;
}

int main() {
    int Arr[] = {1, 2, 4, 1, 3, 4, 2, 5, 6, 5};
    printf("値とインデックスの合計の最大絶対差: %d", maxabsDiff(Arr, 10));
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます −

値とインデックスの合計の最大絶対差: 13

補足: O(n) での最適化

絶対値の式は、i と j の大小関係に応じて絶対値を外すことで、次の 4 つの式のいずれかに分解できます。

• (Arr[i] + i) − (Arr[j] + j)
• (Arr[j] + j) − (Arr[i] + i)
• (Arr[i] − i) − (Arr[j] − j)
• (Arr[j] − j) − (Arr[i] − i)

したがって、答えは「Arr[i] + i の最大値と最小値の差」と「Arr[i] − i の最大値と最小値の差」のうち大きい方になります。この方法なら配列を 1 回走査するだけで済むため、計算量を O(n) に抑えられ、大きな配列でも高速に動作します。