C++で配列の (arr[i] − i) − (arr[j] − j) の値を最大化する方法

問題文

配列 arr[] が与えられたとき、i ≠ j となる条件のもとで、(arr[i] − i) − (arr[j] − j) の最大値を求めます。ここで、i と j は 0 から n−1 までの範囲をとり、n は入力配列 arr[] のサイズです。

例えば、入力配列が {7, 5, 10, 2, 3} の場合、次のように計算することで最大値 9 を得られます。

(要素10 − インデックス2) − (要素2 − インデックス3)
(10 − 2) − (2 − 3) = 8 − (−1) = 9

考えるポイント

(arr[i] − i) − (arr[j] − j) を最大化するには、「(arr[i] − i) ができるだけ大きく」「(arr[j] − j) ができるだけ小さく」なる組み合わせを見つければよいことになります。つまり、配列全体を一度走査して (arr[i] − i) の最大値と最小値をそれぞれ求め、その差を返せば答えが得られます。

アルゴリズム

1. 配列全体の中から (arr[i] − i) の最大値を求める。
2. 配列全体の中から (arr[i] − i) の最小値を求める。
3. 上記2つの値の差を返す。

この方法なら、配列を一度走査するだけで済むため、時間計算量は O(n)、追加の記憶領域は O(1) で処理できます。

C++による実装例

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

int getMaxDiff(int *arr, int n){
    if (n < 2) {
        cout << "Invalid input" << endl;
        exit(1);
    }
    int minVal = INT_MAX;
    int maxVal = INT_MIN;
    for (int i = 0; i < n; ++i) {
        int result = arr[i] - i;
        if (result > maxVal) {
            cout << "Max = " << arr[i] << " - " << i << endl;
            maxVal = result;
        }
        if (result < minVal) {
            cout << "Min = " << arr[i] << " - " << i << endl;
            minVal = result;
        }
    }
    return (maxVal - minVal);
}

int main(){
    int arr[] = {7, 5, 10, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum value = " << getMaxDiff(arr, n) << endl;
    return 0;
}

出力結果

上記のプログラムをコンパイルして実行すると、以下のような出力が得られます。

Max = 7 - 0
Min = 7 - 0
Min = 5 - 1
Max = 10 - 2
Min = 2 - 3
Maximum value = 9

まとめ

この問題は、式を「(arr[i] − i)」という単位に分解して考えることで、全ペアを調べる O(n²) の総当たりではなく、最大値と最小値の差を使った O(n) の効率的な解法に落とし込めるのがポイントです。配列サイズが大きい場合でも高速に動作するため、実践的で有用なアプローチといえます。