Chênh lệch lớn nhất giữa các phần tử liền kề trong mảng đã sắp xếp trong C++

Cho một mảng chưa sắp xếp. Nhiệm vụ: tìm chênh lệch lớn nhất giữa các phần tử liền kề của mảng đó dưới dạng đã sắp xếp.

Quy trình: Sắp xếp mảng → Tính chênh lệch giữa các cặp liền kề → Tìm giá trị lớn nhất.

Ví dụ 1

Input – Arr[] = [1, 5, 10, 2, 7]

Output – Chênh lệch lớn nhất: 3

Giải thích: Mảng sắp xếp tăng dần: [1, 2, 5, 7, 10]

Arr[1]-Arr[0] = 1, Max = 1
Arr[2]-Arr[1] = 3, Max = 3
Arr[3]-Arr[2] = 2, Max = 3
Arr[4]-Arr[3] = 3, Max = 3

Ví dụ 2

Input – Arr[] = [5, 11, 21, 15, 20]

Output – Chênh lệch lớn nhất: 6

Giải thích: Mảng sắp xếp: [5, 11, 15, 20, 21]

Arr[1]-Arr[0] = 6, Max = 6
Arr[2]-Arr[1] = 4, Max = 6
Arr[3]-Arr[2] = 5, Max = 6
Arr[4]-Arr[3] = 1, Max = 6

Thuật toán

1. Nhập mảng nguyên.
2. Sắp xếp mảng tăng dần (hoặc giảm dần, kết quả chênh lệch tuyệt đối giống nhau).
3. Khởi tạo MaxD = Arr[1] - Arr[0].
4. Duyệt từ i = 1 đến size-2, cập nhật MaxD = max(MaxD, Arr[i+1] - Arr[i]).
5. Trả về MaxD.

Ví dụ code

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

int maxAdjDiff(int A[], int size) {
    sort(A, A + size); // Sắp xếp tăng dần
    int MaxD = A[1] - A[0];
    for (int i = 1; i < size - 1; i++) {
        MaxD = max(MaxD, A[i + 1] - A[i]);
    }
    return MaxD;
}

int main() {
    int Arr[] = {1, 5, 2, 18, 20, 13};
    int size = sizeof(Arr) / sizeof(Arr[0]);
    int md = maxAdjDiff(Arr, size);
    cout << "Maximum adjacent difference in sorted array: " << md << endl;
    return 0;
}

Kết quả

Maximum adjacent difference in sorted array: 8

Giải thích: Mảng sắp xếp: [1, 2, 5, 13, 18, 20]. Chênh lệch: 1, 3, 8, 5, 2. Max = 8 (giữa 5 và 13).

Độ phức tạp: O(n log n) do sắp xếp. Không thể tốt hơn trừ khi dùng counting sort/radix sort cho số nguyên phạm vi nhỏ.