Tìm số lượng phần tử lớn nhất mà hiệu tuyệt đối cặp nào cũng ≤ 1 trong C++

Cho mảng n phần tử. Cần chọn số lượng phần tử lớn nhất sao cho hiệu tuyệt đối giữa bất kỳ hai phần tử nào trong tập chọn đều ≤ 1. Ví dụ: mảng [2, 2, 3, 4, 5], kết quả là 3 (tập {2, 2, 3}).

Hiệu tuyệt đối ≤ 1 nghĩa là các số chỉ có thể là x và x+1. Ý tưởng: đếm tần suất mỗi giá trị, tìm max của (tần suất[x] + tần suất[x+1]).

Ví dụ

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

int maxElem(int arr[], int n) {
    map<int, int> occurrence;
    for (int i = 0; i < n; ++i)
        occurrence[arr[i]]++;
    int ans = 0, key;
    for (auto it = occurrence.begin(); it != occurrence.end(); ++it) {
        key = it->first;
        if (occurrence[key + 1] != 0)
            ans = max(ans, occurrence[key] + occurrence[key + 1]);
    }
    return ans;
}

int main() {
    int arr[] = {2, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Result is: " << maxElem(arr, n);
}

Kết quả

Result is: 3