เราได้รับอาร์เรย์ ไม่ต้องเรียงลำดับอาร์เรย์ ภารกิจคือการค้นหาความแตกต่างสูงสุดระหว่างองค์ประกอบที่อยู่ติดกันของอาร์เรย์นั้นในรูปแบบที่จัดเรียง ดังนั้นสิ่งแรกคือการเรียงลำดับอาร์เรย์ในลำดับที่เพิ่มขึ้นหรือลดลง จากนั้นเราจะวนซ้ำอาร์เรย์และคำนวณผลต่างที่อยู่ติดกันของ Arr[i+1]-Arr[i] จากนั้นสำหรับการทำซ้ำแต่ละครั้ง เราจะเปรียบเทียบความแตกต่างนี้กับความแตกต่างที่พบสูงสุดจนถึงตอนนี้
ป้อนข้อมูล − Arr[] =[ 1,5,10,2,7 ]
ผลลัพธ์ − ค่าความต่างที่อยู่ติดกันสูงสุดของอาร์เรย์ในรูปแบบการเรียงลำดับคือ 3
คำอธิบาย − เรียงลำดับ Arr[] ตามลำดับที่เพิ่มขึ้น =[ 1,2,5,7,10 ] ดังนั้นความแตกต่างที่อยู่ติดกันจึงเป็นดังนี้ -
Arr[1]-Arr[0]=1, Maximum Difference=1 Arr[2]-Arr[1]=3, Maximum Difference=3 Arr[3]-Arr[2]=2, Maximum Difference=3 Arr[4]-Arr[3]=3, Maximum Difference=3
ป้อนข้อมูล − Arr[] =[ 5,11,21,15,20 ]
ผลผลิต − ค่าความต่างที่อยู่ติดกันสูงสุดของอาร์เรย์ในรูปแบบการเรียงลำดับคือ 6
คำอธิบาย − เรียงลำดับ Arr[] ตามลำดับที่เพิ่มขึ้น =[ 5,11,15,20,21 ] ดังนั้นความแตกต่างที่อยู่ติดกันจึงเป็นดังนี้ -
Arr[1]-Arr[0]=6, Maximum Difference=6 Arr[2]-Arr[1]=4, Maximum Difference=6 Arr[3]-Arr[2]=5, Maximum Difference=6 Arr[4]-Arr[3]=1, Maximum Difference=6
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
ใส่อาร์เรย์จำนวนเต็ม Arr[].
-
เรียงลำดับอาร์เรย์ในลำดับที่เพิ่มขึ้น ( การเรียงลำดับไม่สำคัญที่นี่ )
-
ประกาศตัวแปรว่า MaxD ให้เก็บค่าความแตกต่างสูงสุดระหว่างองค์ประกอบที่อยู่ติดกันที่พบจนถึงตอนนี้ ใช้ค่าเริ่มต้นเป็น Arr[1]-Arr[0].
-
เริ่มการวนซ้ำจากองค์ประกอบที่สองจนถึงดัชนีองค์ประกอบสุดท้ายของอาร์เรย์
-
หากความแตกต่างที่คำนวณได้ระหว่าง Arr[i+1]-Arr[i]>MaxD ให้อัปเดต MaxD
-
ทำต่อไปจนกว่าเราจะไปถึงดัชนีองค์ประกอบสุดท้ายที่สอง
-
พิมพ์ผลลัพธ์ MaxD เป็นความแตกต่างขององค์ประกอบที่อยู่ติดกันสูงสุด
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int max_adj_Diff(int A[],int size){
int MaxD=A[1]-A[0];
for(int i=1;i<size-1;i++){
if(A[i+1]-A[i] > MaxD)
MaxD=A[i+1]-A[i];
}
return MaxD;
}
int main(){
int Arr[]={1,5,2,18,20,13};
sort(Arr,6); //this is supposed to sort array in increasing order
int md=max_adj_Diff(Arr,6);
cout<<"Maximum adjacent difference in array in its sorted form :"<<md;
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Maximum adjacent difference in array in its sorted form: 8
