C言語：大きい要素が小さい数の後に現れるときの、2つの要素間の最大差を求める方法

問題の概要

サイズNの整数配列が与えられます。配列にはランダムな順序で整数が含まれています。この課題は、より大きい要素がより小さい数の後に現れるという条件を満たす、2つの要素間の最大差を見つけることです。つまり、Arr[j] − Arr[i] が最大になる組み合わせを求めます（ただし j > i）。

例1

入力：

Arr[] = { 2,1,3,8,3,19,21 }

出力： 大きい要素が小さい数の後に現れる2つの要素間の最大差 ― 20

説明： 最大差は21と1の間であり、配列の中で21は1の後に現れています。

例2

入力：

Arr[] = { 18, 2,8,1,2,3,2,6 }

出力： 大きい要素が小さい数の後に現れる2つの要素間の最大差 ― 6

説明： 最大差は8と2の間であり、配列の中で8は2の後に現れています。

プログラムで使用しているアプローチ

• 整数型の配列（Arr[]）と、そのサイズを格納する変数（n）を宣言します。

• 関数 maxDiff(int arr[], int n) を使用して、条件を満たす最大差を計算します。引数として入力配列とそのサイズを受け取ります。

• maxDiff() 内では、「これまでに見つかった最大差」を格納する変数 MD と、「これまでに訪れた最小値」を格納する変数 min を宣言します。

• 初期値として、MD = arr[1] − arr[0]、min = arr[0] を設定します。

• ループ処理の中で、まず arr[i] − min が MD より大きければ、MD を更新します。

• 続いて、arr[i] が min より小さければ、min を更新します。

• この方法により、常に「現在の要素より前方に出現した最小値」との差を計算できるため、時間計算量 O(n)、空間計算量 O(1) の効率的な解法になります。

• 最終的に MD を結果として返します。

コード例

#include <stdio.h>
int maxDiff(int arr[], int n){
    // Maximum difference found so far
    int MD = arr[1] - arr[0];
    // Minimum number visited so far
    int min = arr[0];
    for(int i = 1; i < n; i++){
        if (arr[i] - min > MD)
            MD = arr[i] - min;
        if (arr[i] < min)
            min = arr[i];
    }
    return MD;
}
/* Driver program to test above function */
int main(){
    int arr[] = {2,5,7,3,4,12};
    int n=6;
    // Function calling
    printf("Maximum difference is : %d ",maxDiff(arr, n));
    return 0;
}

出力

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

The maximum difference between two elements such that the larger element appears after the smaller number : 10