Chênh lệch liền kề tối đa trong một mảng ở dạng được sắp xếp trong C ++

Chúng ta được cung cấp với một mảng. Mảng không cần được sắp xếp. Nhiệm vụ là tìm ra sự khác biệt lớn nhất giữa các phần tử liền kề của mảng đó ở dạng đã sắp xếp của nó. Vì vậy, điều đầu tiên là sắp xếp mảng theo thứ tự tăng hoặc giảm. Sau đó, chúng ta sẽ lặp lại mảng và tính hiệu số lân cận của Arr [i + 1] -Arr [i]. Sau đó, đối với mỗi lần lặp, chúng tôi sẽ so sánh sự khác biệt này với sự khác biệt được tìm thấy tối đa cho đến nay.

Đầu vào - Arr [] =[1,5,10,2,7]

Đầu ra - Hiệu số liền kề tối đa trong mảng ở dạng đã sắp xếp của nó là 3.

Giải thích - Đã sắp xếp Arr [] theo thứ tự tăng dần =[1,2,5,7,10]. Vì vậy, sự khác biệt liền kề như sau -

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

Đầu vào - Arr [] =[5,11,21,15,20]

Đầu ra - Hiệu số liền kề tối đa trong mảng ở dạng đã sắp xếp của nó là 6.

Giải thích - Đã sắp xếp Arr [] theo thứ tự tăng dần =[5,11,15,20,21]. Vì vậy, sự khác biệt liền kề như sau -

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

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Nhập một mảng số nguyên Arr [].
Sắp xếp mảng theo thứ tự tăng dần. (Thứ tự sắp xếp không quan trọng ở đây)
Khai báo một biến MaxD để lưu trữ sự khác biệt lớn nhất giữa các phần tử liền kề được tìm thấy cho đến nay. Lấy giá trị ban đầu của nó là Arr [1] -Arr [0].
Bắt đầu vòng lặp, từ phần tử thứ hai cho đến chỉ mục phần tử cuối cùng của mảng.
Nếu sự khác biệt được tính toán giữa Arr [i + 1] -Arr [i]> MaxD, hãy cập nhật MaxD.
Tiếp tục điều này cho đến khi chúng tôi đạt đến chỉ mục phần tử cuối cùng thứ hai.
In kết quả MaxD dưới dạng hiệu số phần tử liền kề lớn nhất.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Maximum adjacent difference in array in its sorted form: 8