【C++】配列内の異なる2つの数値のインデックス間の最大差を求めるプログラム

この問題では、n個の整数で構成される配列 arr[] が与えられます。目的は、値が互いに異なる任意の2つの要素を選んだときに、そのインデックス間の差の最大値を求めることです。

問題の概要

ここで必要なのは、配列内の整数値の中から「異なる値を持つ2つの要素」を選び、それらのインデックスの差が最大になる組み合わせを見つけることです。

入力例

arr[] = {4, 1, 3, 2, 1, 2, 4}

出力例

5

説明

インデックス0の要素「4」と、インデックス5の要素「2」を比較すると、インデックスの差は 5 − 0 = 5 となり、これが最大値となります。

解法のアプローチ

この問題は、各要素を先頭の要素 a[0] と比較することで効率的に解けます。手順は以下の通りです。

1. 左側から走査し、a[0] と異なる値を持つ最初のインデックスを見つけます。
2. 次に右側から走査し、a[0] と異なる値を持つ最初のインデックスを見つけます。
3. 2つのインデックスの差を比較し、大きい方を答えとして返します。

なお、末尾の要素を基準にして同じ考え方を適用することでも解くことができます。

実装例

#include <iostream>
using namespace std;

int maximum(int a, int b){
    if(a > b)
        return a;
    return b;
}

int CalcMaxIndDiff(int a[], int n) {
    int indDiff1 = 0, indDiff2 = 0;
    int i = 0;

    // 左側から、先頭の要素と異なる値を持つインデックスを探索
    while(i < (n - 1)){
        if(a[0] != a[i]){
            indDiff2 = i;
            break;
        }
        i++;
    }

    // 右側から、先頭の要素と異なる値を持つインデックスを探索
    i = (n - 1);
    while(i > 0){
        if(a[0] != a[i]){
            indDiff1 = i;
            break;
        }
        i--;
    }

    return maximum(indDiff1, indDiff2);
}

int main() {
    int arr[] = { 4, 1, 3, 2, 1, 2, 4 };
    int n = 7;
    cout<<"異なる2つの数値のインデックス間の最大差は "<<CalcMaxIndDiff(arr, n);
    return 0;
}

出力

異なる2つの数値のインデックス間の最大差は 5

計算量

時間計算量：O(n) ― 配列を最大2回走査するだけで済むため、線形時間で処理が完了します。
空間計算量：O(1) ― 使用する追加メモリは定数個の変数のみです。

まとめ

配列の両端からそれぞれ「基準の要素と異なる値」が現れる位置を探すことで、全ペアを総当たりする O(n²) の手法を使わずに、O(n) で最大のインデックス差を求められます。配列操作の基本的な走査テクニックとして、ぜひ押さえておきましょう。