สมมติว่าเรามีอาร์เรย์ขององค์ประกอบ n เราต้องหาจำนวนองค์ประกอบสูงสุดเพื่อเลือกจากอาร์เรย์ เพื่อให้ผลต่างระหว่างสององค์ประกอบที่เลือกมีค่าน้อยกว่าหรือเท่ากับ 1 ดังนั้นหากอาร์เรย์เป็นแบบ [2, 2, 3, 4, 5] จากนั้นองค์ประกอบจะเป็น 3 ดังนั้นลำดับที่มีการนับสูงสุดคือ 2, 2, 3
ความแตกต่างแน่นอนของ 0 และ 1 หมายความว่าตัวเลขสามารถเป็นประเภท x และ x + 1 ได้ ดังนั้นแนวคิดคือการจัดเก็บความถี่ขององค์ประกอบอาร์เรย์ ดังนั้นหากเราพบผลรวมสูงสุดของสององค์ประกอบที่ต่อเนื่องกัน ก็จะเป็นคำตอบ
ตัวอย่าง
#include <iostream>
#include <map>
using namespace std;
int maxElem(int arr[], int n) {
map<int,int> occurrence;
for(int i=0;i<n;++i){
if(occurrence[arr[i]])
occurrence[arr[i]] += 1;
else
occurrence[arr[i]] = 1;
}
int ans = 0, key;
map<int,int>:: iterator it=occurrence.begin();
while(it!=occurrence.end()) {
key = it->first;
++it;
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
