Encuentre el número máximo de elementos tales que su diferencia absoluta sea menor o igual a 1

Dada una array de n elementos, encuentre el número máximo de elementos para seleccionar de la array tal que la diferencia absoluta entre dos de los elementos elegidos sea menor o igual a 1.
Ejemplos : 

Input : arr[] = {1, 2, 3}
Output : 2
We can either take 1, 2 or 2, 3.
Both will have the count 2 so maximum count is 2

Input : arr[] = {2, 2, 3, 4, 5}
Output : 3
The sequence with maximum count is 2, 2, 3.

La diferencia absoluta de 0 o 1 significa que los números elegidos pueden ser del tipo x y x+1. Por lo tanto, la idea es almacenar frecuencias de elementos de array. Entonces, la tarea ahora se reduce a encontrar la suma máxima de dos elementos consecutivos cualesquiera.
A continuación se muestra la implementación del enfoque anterior:  

// CPP program to find maximum number of
// elements such that their absolute
// difference is less than or equal to 1
#include <bits/stdc++.h>
using namespace std;
 
// function to return maximum number of elements
int maxCount(int n,int a[])
{
    // Counting frequencies of elements
    map<int,int> freq;
 
    for(int i=0;i<n;++i){
        if(freq[a[i]])
            freq[a[i]] += 1;
        else
            freq[a[i]] = 1;
    }
 
    // Finding max sum of adjacent indices
    int ans = 0, key;
 
    map<int,int>:: iterator it=freq.begin();
 
    while(it!=freq.end())
    {
        key = it->first;
 
        // increment the iterator
        ++it;
 
        if(freq[key+1]!=0)
            ans=max(ans,freq[key]+freq[key+1]);
 
    }
 
    return ans;
}
 
// Driver Code
int main(){
    int n = 5;
    int arr[] = {2, 2, 3, 4, 5};
 
    // function call to print required answer
    cout<<maxCount(n,arr);
 
    return 0;
}
 
 
// This code is contributed by Sanjit_Prasad

// Java program to find the maximum number
// of elements such that their absolute
// difference is less than or equal to 1
import java.util.HashMap;
import java.util.Map;
import java.lang.Math;
 
class GfG
{
 
    // function to return the maximum number of elements
    static int maxCount(int n,int a[])
    {
        // Counting frequencies of elements
        HashMap<Integer, Integer> freq = new HashMap<>();
     
        for(int i = 0; i < n; ++i)
        {
            if(freq.containsKey(a[i]))
                freq.put(a[i], freq.get(a[i]) + 1);
            else
                freq.put(a[i], 1);
        }
     
        // Finding max sum of adjacent indices
        int ans = 0;
     
        for (Integer key : freq.keySet())
        {
            if(freq.containsKey(key+1))
                ans = Math.max(ans, freq.get(key) + freq.get(key+1));
        }
     
        return ans;
    }
 
    // Driver code
    public static void main(String []args)
    {
         
        int n = 5;
        int arr[] = {2, 2, 3, 4, 5};
     
        // function call to print required answer
        System.out.println(maxCount(n,arr));
    }
}
 
// This code is contributed by Rituraj Jain

# Python program to find maximum number of
# elements such that their absolute
# difference is less than or equal to 1
 
def maxCount(a):
 
    # Counting frequencies of elements
    freq = {}
    for i in range(n):
        if (a[i] in freq):
            freq[a[i]] += 1
        else:
            freq[a[i]] = 1
         
     
    # Finding max sum of adjacent indices   
    ans = 0
    for key, value in freq.items():
        if (key+1 in freq) :   
            ans = max(ans, freq[key] + freq[key + 1])
     
    return ans
     
# Driver Code
n = 5
arr = [2, 2, 3, 4, 5]
 
print(maxCount(arr))

// C# program to find the maximum number
// of elements such that their absolute
// difference is less than or equal to 1
using System;
using System.Collections.Generic;
 
class GfG
{
 
    // function to return the maximum number of elements
    static int maxCount(int n,int []a)
    {
        // Counting frequencies of elements
        Dictionary<int,int> mp = new Dictionary<int,int>();
         
        // Increase the frequency of elements
        for (int i = 0 ; i < n; i++)
        {
            if(mp.ContainsKey(a[i]))
            {
                var val = mp[a[i]];
                mp.Remove(a[i]);
                mp.Add(a[i], val + 1);
            }
            else
            {
                mp.Add(a[i], 1);
            }
        }
     
        // Finding max sum of adjacent indices
        int ans = 0;
     
        foreach(KeyValuePair<int, int> e in mp)
        {
            if(mp.ContainsKey(e.Key+1))
                ans = Math.Max(ans, mp[e.Key] + mp[e.Key+1]);
        }
     
        return ans;
    }
 
    // Driver code
    public static void Main(String []args)
    {
         
        int n = 5;
        int []arr = {2, 2, 3, 4, 5};
     
        // function call to print required answer
        Console.WriteLine(maxCount(n,arr));
    }
}
 
/* This code is contributed by PrinciRaj1992 */

<script>
 
// JavaScript program to find maximum number of
// elements such that their absolute
// difference is less than or equal to 1
 
// function to return maximum number of elements
function maxCount(n,a)
{
    // Counting frequencies of elements
    var freq = new Map();
 
    for(var i=0;i<n;++i){
        if(freq.has(a[i]))
            freq.set(a[i], freq.get(a[i])+1)
        else
            freq.set(a[i], 1)
    }
 
    // Finding max sum of adjacent indices
    var ans = 0, key;
 
    freq.forEach((value, key) => {
        
        if(freq.has(key+1))
            ans=Math.max(ans,freq.get(key)+freq.get(key+1));
    });
 
    return ans;
}
 
// Driver Code
 
var n = 5;
var arr =  [2, 2, 3, 4, 5];
 
// function call to print required answer
document.write( maxCount(n,arr));
 
</script>

3

Complejidad de tiempo: O(n * log(n))

Espacio Auxiliar: O(n)