C++에서 절대 차이가 1보다 작거나 같은 요소의 최대 수 찾기

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