Đếm phần tử tối đa mảng chênh tuyệt đối không vượt K trong C++

Cho mảng arr[] và số nguyên k. Tìm số lượng phần tử lớn nhất trong một tập con sao cho chênh lệch tuyệt đối giữa bất kỳ cặp nào không vượt quá k.

Ví dụ

arr = {2, 3, 6, 12, 14}, k = 5 → tập con {2, 3, 6} → 3 phần tử

arr = {2, 3, 6, 12, 14}, k = 10 → tập con {2, 3, 6, 12} → 4 phần tử

k = 0 → 0 (không có cặp nào chênh lệch 0)

Phương pháp (Sắp xếp + Cửa sổ trượt)

• Sắp xếp mảng.
• Duyệt i từ 0 đến n-1, mở rộng j cho đến khi arr[j] > arr[i] + k.
• Cập nhật max_count = max(max_count, j - i).

Ví dụ minh họa (C++)

#include <iostream>
#include <algorithm>
using namespace std;

int countmax(int arr[], int size, int K) {
    int result = 0;
    int i = 0, j = 0;
    sort(arr, arr + size);
    for (i = 0; i < size; i++) {
        while (j < size && arr[j] <= arr[i] + K) j++;
        if (result < (j - i)) result = j - i;
    }
    return result;
}

int main() {
    int arr[] = { 2, 3, 6, 12, 14 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int K = 5;
    cout << "count is " << countmax(arr, size, K) << endl;
    return 0;
}

Đầu ra

count is 3