C++で配列内の最大ギャップ（最大値と最小値の差）を求める方法

このチュートリアルでは、与えられた配列の中から2つの要素間の最大の差（最大ギャップ）を求めるプログラムをC++で作成します。アプローチは非常にシンプルで、配列内の最大値と最小値を見つけ、その差を計算するだけです。

解決の手順

• 配列を初期化します。
• 配列内の最大値と最小値を見つけます。
• 「最大値 − 最小値」を計算して返します。

サンプルコード

それでは、実際のコードを見てみましょう。

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

int findLargestGap(int arr[], int n) {
    int maxVal = arr[0], minVal = arr[0];
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
        if (arr[i] < minVal) {
            minVal = arr[i];
        }
    }
    return maxVal - minVal;
}

int main() {
    int arr[] = {3, 4, 1, 6, 5, 6, 9, 10};
    cout << findLargestGap(arr, 8) << endl;
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、以下の出力が得られます。

9

処理の流れの解説

このプログラムでは、まず配列の最初の要素を最大値・最小値の初期値として設定します。その後、forループで全要素を一度だけ走査し、より大きな値が見つかれば最大値を、より小さな値が見つかれば最小値を更新していきます。最後に maxVal - minVal を返すことで、配列内の要素間の最大差が求まります。

今回の例では、配列 {3, 4, 1, 6, 5, 6, 9, 10} の最大値は 10、最小値は 1 であるため、出力は 10 - 1 = 9 となります。

なお、このアルゴリズムの時間計算量は O(n)、空間計算量は O(1) であり、配列を1回走査するだけで済むため非常に効率的です。また、変数名に標準ライブラリの std::max / std::min と紛らわしい名前を使わないよう、maxVal / minVal としています。

まとめ

配列の最大ギャップを求める問題は、「最大値と最小値を見つけて差を取る」という基本テクニックだけで解決できる好例です。ソートを行う必要がないため、線形時間で処理できます。本チュートリアルについてご不明な点がある場合は、コメント欄でお気軽にお尋ねください。