หาจำนวนสมาชิกสูงสุดที่ความต่างสัมบูรณ์ ≤ 1 ใน C++

โจทย์

ให้อาร์เรย์ n ตัว ต้องการเลือกสมาชิกมากที่สุดที่ความต่างสัมบูรณ์ระหว่างคู่ใดคู่หนึ่ง ≤ 1

ตัวอย่าง: [2, 2, 3, 4, 5] → เลือกได้ 3 ตัว (2, 2, 3)

ข้อสังเกต

ความต่าง ≤ 1 หมายถึงตัวเลขต้องเป็น x และ x+1 เท่านั้น → หา max ของ (freq[x] + freq[x+1])

ตัวอย่างโค้ด C++

#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;
    for (auto it = occurrence.begin(); it != occurrence.end(); ++it) {
        int 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);
}

ผลลัพธ์

Result is: 3