La subsecuencia más larga tal que la diferencia absoluta entre cada par es como máximo 1

Dada una array de enteros arr[] de tamaño N , la tarea es encontrar la subsecuencia más larga S tal que para todo a[i], a[j] ∈ S y |a[i] – a[j]| ≤ 1 .

Ejemplos:  

Entrada: arr[] = {2, 2, 3, 5, 5, 6, 6, 6} 
Salida: 5 
Explicación: 
Hay 2 subsecuencias tales que la diferencia entre cada par es como máximo 1 
{2, 2, 3} y {5, 5, 6, 6, 6} 
El más largo de estos es {5, 5, 6, 6, 6} con una longitud de 5.

Entrada: arr[] = {5, 7, 6, 4, 4, 2} 
Salida: 3 

Planteamiento:
La idea es observar que para una subsucesión con una diferencia entre todos los pares posibles a lo sumo uno es posible cuando la subsucesión contiene elementos entre [X , X + 1].

• Inicialice la longitud máxima de la subsecuencia requerida a 0.
• Cree un HashMap para almacenar la frecuencia de cada elemento de la array.
• Iterar a través del mapa hash y para cada elemento a[i] en el mapa hash: 
  • Encuentre el recuento de ocurrencias del elemento (a[i] + 1), (a[i]) y (a[i] – 1).
  • Encuentre el recuento máximo de ocurrencia de elementos (a[i] + 1) o (a[i] – 1).
  • Si el recuento total de ocurrencias es mayor que la longitud máxima encontrada, actualice la longitud máxima de la subsecuencia.

A continuación se muestra la implementación del enfoque anterior. 

// Java implementation for
// Longest subsequence such that absolute
// difference between every pair is atmost 1
 
import java.util.*;
public class GeeksForGeeks {
    public static int longestAr(
            int n, int arr[]){
        Hashtable<Integer, Integer> count
            = new Hashtable<Integer, Integer>();
 
        // Storing the frequency of each
        // element in the hashtable count
        for (int i = 0; i < n; i++) {
            if (count.containsKey(arr[i]))
                count.put(arr[i], count.get(
                    arr[i]) + 1
                );
            else
                count.put(arr[i], 1);
        }
 
        Set<Integer> kset = count.keySet();
        Iterator<Integer> it = kset.iterator();
 
        // Max is used to keep a track of
        // maximum length of the required
        // subsequence so far.
        int max = 0;
 
        while (it.hasNext()) {
            int a = (int)it.next();
            int cur = 0;
            int cur1 = 0;
            int cur2 = 0;
 
            // Store frequency of the
            // given element+1.
            if (count.containsKey(a + 1))
                cur1 = count.get(a + 1);
 
            // Store frequency of the
            // given element-1.
            if (count.containsKey(a - 1))
                cur2 = count.get(a - 1);
 
            // cur store the longest array
            // that can be formed using a.
            cur = count.get(a) +
                  Math.max(cur1, cur2);
 
            // update max if cur>max.
            if (cur > max)
                max = cur;
        }
 
        return (max);
    }
     
    // Driver Code
    public static void main(String[] args)
    {
        int n = 8;
        int arr[] = { 2, 2, 3, 5, 5, 6, 6, 6 };
        int maxLen = longestAr(n, arr);
        System.out.println(maxLen);
    }
}

# Python3 implementation for
# Longest subsequence such that absolute
# difference between every pair is atmost 1
 
def longestAr(n, arr):
    count = dict()
 
    # Storing the frequency of each
    # element in the hashtable count
    for i in arr:
        count[i] = count.get(i, 0) + 1
 
    kset = count.keys()
 
    # Max is used to keep a track of
    # maximum length of the required
    # subsequence so far.
    maxm = 0
 
    for it in list(kset):
        a = it
        cur = 0
        cur1 = 0
        cur2 = 0
 
        # Store frequency of the
        # given element+1.
        if ((a + 1) in count):
            cur1 = count[a + 1]
 
        # Store frequency of the
        # given element-1.
        if ((a - 1) in count):
            cur2 = count[a - 1]
 
        # cur store the longest array
        # that can be formed using a.
        cur = count[a] + max(cur1, cur2)
 
        # update maxm if cur>maxm.
        if (cur > maxm):
            maxm = cur
 
    return maxm
 
# Driver Code
if __name__ == '__main__':
    n = 8
    arr = [2, 2, 3, 5, 5, 6, 6, 6]
    maxLen = longestAr(n, arr)
    print(maxLen)
 
# This code is contributed by mohit kumar 29

<script>
// Javascript implementation for
// Longest subsequence such that absolute
// difference between every pair is atmost 1
 
function longestAr(n,arr)
{
    let count = new Map();
   
        // Storing the frequency of each
        // element in the hashtable count
        for (let i = 0; i < n; i++) {
            if (count.has(arr[i]))
                count.set(arr[i], count.get(
                    arr[i]) + 1
                );
            else
                count.set(arr[i], 1);
        }
   
         
   
        // Max is used to keep a track of
        // maximum length of the required
        // subsequence so far.
        let max = 0;
   
        for(let it of count.keys()) {
            let a = it;
            let cur = 0;
            let cur1 = 0;
            let cur2 = 0;
   
            // Store frequency of the
            // given element+1.
            if (count.has(a + 1))
                cur1 = count.get(a + 1);
   
            // Store frequency of the
            // given element-1.
            if (count.has(a - 1))
                cur2 = count.get(a - 1);
   
            // cur store the longest array
            // that can be formed using a.
            cur = count.get(a) +
                  Math.max(cur1, cur2);
   
            // update max if cur>max.
            if (cur > max)
                max = cur;
        }
   
        return (max);
}
 
// Driver Code
let n = 8;
let arr=[2, 2, 3, 5, 5, 6, 6, 6];
let maxLen = longestAr(n, arr);
document.write(maxLen);
         
 
 
// This code is contributed by unknown2108
</script>

5

Complejidad temporal: O(n). 
Complejidad espacial: O(n).