C++で絶対差が1以下になるような要素の最大数を見つけます

n個の要素の配列があるとします。配列から選択する要素の最大数を見つけて、選択した要素の任意の2つの間の絶対差が1以下になるようにする必要があります。したがって、配列が[2、2、3、4、 5]の場合、要素は3になるため、最大カウントのシーケンスは2、2、3になります。

0と1の絶対差は、数値がx型とx + 1型である可能性があることを意味します。したがって、配列要素の頻度を格納するという考え方です。したがって、2つの連続する要素の最大合計が見つかった場合、それが解決策になります。

例

#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