Subsecuencia más larga tal que la diferencia entre adyacentes es uno | conjunto 2

Dada una array de tamaño n . La tarea es encontrar la subsecuencia más larga tal que la diferencia entre los adyacentes sea uno. Se requiere la complejidad temporal de O(n).
Ejemplos: 
 

Input :  arr[] = {10, 9, 4, 5, 4, 8, 6}
Output :  3
As longest subsequences with difference 1 are, "10, 9, 8", 
"4, 5, 4" and "4, 5, 6".

Input :  arr[] = {1, 2, 3, 2, 3, 7, 2, 1}
Output :  7
As longest consecutive sequence is "1, 2, 3, 2, 3, 2, 1".

Método 1: Previamente, en esta publicación se discutió un enfoque que tiene una complejidad temporal de O(n ² ) . Método 2 (Enfoque eficiente): la idea es crear un mapa hash que tenga tuplas en la forma (ele, len) , donde len denota la longitud de la subsecuencia más larga que termina con el elemento ele . Ahora, para cada elemento arr[i] podemos encontrar la longitud de los valores arr[i]-1 y arr[i]+1 en la tabla hash y considerar el máximo entre ellos. Sea este valor máximo max . Ahora, la longitud de la subsecuencia más larga que termina con arr[i] sería max+1
. Actualice esta longitud junto con el elemento arr[i] en la tabla hash. Finalmente, el elemento que tiene la longitud máxima en la tabla hash da la subsecuencia de mayor longitud.
 

// C++ implementation to find longest subsequence
// such that difference between adjacents is one
#include <bits/stdc++.h>
using namespace std;
   
// function to find longest subsequence such
// that difference between adjacents is one
int longLenSub(int arr[], int n)
{
    // hash table to map the array element with the
    // length of the longest subsequence of which
    // it is a part of and is the last element of
    // that subsequence
    unordered_map<int, int> um;
      
    // to store the longest length subsequence
    int longLen = 0;
      
    // traverse the array elements
    for (int i=0; i<n; i++)
    {
        // initialize current length
        // for element arr[i] as 0
        int len = 0;
          
        // if 'arr[i]-1' is in 'um' and its length 
        // of subsequence is greater than 'len'
        if (um.find(arr[i]-1) != um.end() &&
            len < um[arr[i]-1])
            len = um[arr[i]-1];
          
        // if 'arr[i]+1' is in 'um' and its length 
        // of subsequence is greater than 'len'       
        if (um.find(arr[i]+1) != um.end() &&
            len < um[arr[i]+1])
            len = um[arr[i]+1];   
          
        // update arr[i] subsequence length in 'um'   
        um[arr[i]] = len + 1;
          
        // update longest length
        if (longLen < um[arr[i]])   
            longLen = um[arr[i]];
    }
       
    // required longest length subsequence
    return longLen;       
}
   
// Driver program to test above
int main()
{
    int arr[] = {1, 2, 3, 4, 5, 3, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Longest length subsequence = "
         << longLenSub(arr, n);
    return 0;
}  

// Java implementation to find longest subsequence
// such that difference between adjacents is one
import java.util.*;
 
class GFG
{
     
// function to find longest subsequence such
// that difference between adjacents is one
static int longLenSub(int []arr, int n)
{
    // hash table to map the array element with the
    // length of the longest subsequence of which
    // it is a part of and is the last element of
    // that subsequence
    HashMap<Integer,
            Integer> um = new HashMap<Integer,
                                      Integer>();
     
    // to store the longest length subsequence
    int longLen = 0;
     
    // traverse the array elements
    for (int i = 0; i < n; i++)
    {
        // initialize current length
        // for element arr[i] as 0
        int len = 0;
         
        // if 'arr[i]-1' is in 'um' and its length
        // of subsequence is greater than 'len'
        if (um.containsKey(arr[i] - 1) &&
              len < um.get(arr[i] - 1))
              len = um.get(arr[i] - 1);
         
        // if 'arr[i]+1' is in 'um' and its length
        // of subsequence is greater than 'len'    
        if (um.containsKey(arr[i] + 1) &&
              len < um.get(arr[i] + 1))
              len = um.get(arr[i] + 1);
         
        // update arr[i] subsequence length in 'um'
        um. put(arr[i], len + 1);
         
        // update longest length
        if (longLen < um.get(arr[i]))
            longLen = um.get(arr[i]);
    }
         
    // required longest length subsequence
    return longLen;    
}
     
// Driver Code
public static void main(String[] args)
{
    int[] arr = {1, 2, 3, 4, 5, 3, 2};
    int n = arr.length;
    System.out.println("Longest length subsequence = " +
                                    longLenSub(arr, n));
}
}
 
// This code is contributed by Princi Singh

# Python3 implementation to find longest
# subsequence such that difference between
# adjacents is one
from collections import defaultdict
 
# function to find longest subsequence such
# that difference between adjacents is one
def longLenSub(arr, n):
 
    # hash table to map the array element
    # with the length of the longest
    # subsequence of which it is a part of
    # and is the last element of that subsequence
    um = defaultdict(lambda:0)
    longLen = 0
    for i in range(n):
 
        # / initialize current length
        # for element arr[i] as 0
        len1 = 0
 
        # if 'arr[i]-1' is in 'um' and its length
        # of subsequence is greater than 'len'
        if (arr[i - 1] in um and
            len1 < um[arr[i] - 1]):
            len1 = um[arr[i] - 1]
 
        # f 'arr[i]+1' is in 'um' and its length
        # of subsequence is greater than 'len'    
        if (arr[i] + 1 in um and
            len1 < um[arr[i] + 1]):
            len1 = um[arr[i] + 1]
 
        # update arr[i] subsequence
        # length in 'um'    
        um[arr[i]] = len1 + 1
 
        # update longest length
        if longLen < um[arr[i]]:
            longLen = um[arr[i]]
 
    # required longest length
    # subsequence
    return longLen
 
# Driver code
arr = [1, 2, 3, 4, 5, 3, 2]
n = len(arr)
print("Longest length subsequence =",
                  longLenSub(arr, n))
 
# This code is contributed by Shrikant13

// C# implementation to find longest subsequence
// such that difference between adjacents is one
using System;
using System.Collections.Generic;
 
class GFG
{
     
// function to find longest subsequence such
// that difference between adjacents is one
static int longLenSub(int []arr, int n)
{
    // hash table to map the array element with the
    // length of the longest subsequence of which
    // it is a part of and is the last element of
    // that subsequence
    Dictionary<int,
               int> um = new Dictionary<int,
                                        int>();
     
    // to store the longest length subsequence
    int longLen = 0;
     
    // traverse the array elements
    for (int i = 0; i < n; i++)
    {
        // initialize current length
        // for element arr[i] as 0
        int len = 0;
         
        // if 'arr[i]-1' is in 'um' and its length
        // of subsequence is greater than 'len'
        if (um.ContainsKey(arr[i] - 1) &&
            len < um[arr[i] - 1])
            len = um[arr[i] - 1];
         
        // if 'arr[i]+1' is in 'um' and its length
        // of subsequence is greater than 'len'    
        if (um.ContainsKey(arr[i] + 1) &&
            len < um[arr[i] + 1])
            len = um[arr[i] + 1];
         
        // update arr[i] subsequence length in 'um'
        um[arr[i]] = len + 1;
         
        // update longest length
        if (longLen < um[arr[i]])
            longLen = um[arr[i]];
    }
         
    // required longest length subsequence
    return longLen;    
}
     
// Driver program to test above
static void Main()
{
    int[] arr = {1, 2, 3, 4, 5, 3, 2};
    int n = arr.Length;
    Console.Write("Longest length subsequence = " +
                               longLenSub(arr, n));
}
}
 
// This code is contributed by Mohit Kumar

<script>
 
// JavaScript implementation to find longest subsequence
// such that difference between adjacents is one
     
    // function to find longest subsequence such
// that difference between adjacents is one
    function longLenSub(arr,n)
    {
        // hash table to map the array element with the
    // length of the longest subsequence of which
    // it is a part of and is the last element of
    // that subsequence
    let um = new Map();
       
    // to store the longest length subsequence
    let longLen = 0;
       
    // traverse the array elements
    for (let i = 0; i < n; i++)
    {
        // initialize current length
        // for element arr[i] as 0
        let len = 0;
           
        // if 'arr[i]-1' is in 'um' and its length
        // of subsequence is greater than 'len'
        if (um.has(arr[i] - 1) &&
              len < um.get(arr[i] - 1))
              len = um.get(arr[i] - 1);
           
        // if 'arr[i]+1' is in 'um' and its length
        // of subsequence is greater than 'len'    
        if (um.has(arr[i] + 1) &&
              len < um.get(arr[i] + 1))
              len = um.get(arr[i] + 1);
           
        // update arr[i] subsequence length in 'um'
        um.set(arr[i], len + 1);
           
        // update longest length
        if (longLen < um.get(arr[i]))
            longLen = um.get(arr[i]);
    }
           
    // required longest length subsequence
    return longLen;    
    }
     
    // Driver Code
    let arr=[1, 2, 3, 4, 5, 3, 2];
    let n = arr.length;
    document.write("Longest length subsequence = " +
                                    longLenSub(arr, n));
     
 
// This code is contributed by unknown2108
 
</script>

Producción:  

Longest length subsequence = 6

Complejidad temporal: O(n). 
Espacio Auxiliar: O(n).
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.