Tìm số phần tử tối đa sao cho hiệu số tuyệt đối của chúng nhỏ hơn hoặc bằng 1 trong C ++

Giả sử chúng ta có một mảng gồm n phần tử. Chúng ta phải tìm số phần tử tối đa để chọn từ mảng sao cho hiệu số tuyệt đối giữa hai phần tử bất kỳ đã chọn nhỏ hơn hoặc bằng 1. Vì vậy, nếu mảng giống như [2, 2, 3, 4, 5], thì phần tử sẽ là 3, do đó, dãy có số đếm tối đa là 2, 2, 3.

Sự khác biệt tuyệt đối của 0 và 1 có nghĩa là số có thể thuộc kiểu x và x + 1. Vì vậy, ý tưởng là lưu trữ tần số của các phần tử mảng. Vì vậy, nếu chúng ta tìm thấy tổng lớn nhất của hai phần tử liên tiếp bất kỳ, nó sẽ là nghiệm.

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){
      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);
}

Đầu ra

Result is: 3