Subsecuencia de longitud máxima con diferencia entre elementos adyacentes como 0 o 1 | conjunto 2

Dada una array de n enteros. El problema es encontrar la longitud máxima de la subsecuencia con una diferencia entre los elementos adyacentes de la subsecuencia como 0 o 1. Se requiere la complejidad temporal de O(n).

Ejemplos: 

Input : arr[] = {2, 5, 6, 3, 7, 6, 5, 8}
Output : 5
The subsequence is {5, 6, 7, 6, 5}.

Input : arr[] = {-2, -1, 5, -1, 4, 0, 3}
Output : 4
The subsequence is {-2, -1, -1, 0}.

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, arr[i] 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 longitud máxima.

Implementación:

// C++ implementation to find maximum length
// subsequence with difference between adjacent
// elements as either 0 or 1
#include <bits/stdc++.h>
using namespace std;
  
// function to find maximum length subsequence
// with difference between adjacent elements as
// either 0 or 1
int maxLenSub(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 maximum length subsequence
    int maxLen = 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]' is in 'um' and its length of
        // subsequence is greater than 'len'   
        if (um.find(arr[i]) != um.end() && len < um[arr[i]])
            len = um[arr[i]];
             
        // 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 maximum length
        if (maxLen < um[arr[i]])   
            maxLen = um[arr[i]];
    }
      
    // required maximum length subsequence
    return maxLen;       
}
  
// Driver program to test above
int main()
{
    int arr[] = {2, 5, 6, 3, 7, 6, 5, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum length subsequence = "
         << maxLenSub(arr, n);
    return 0;
}

// Java implementation to find maximum length
// subsequence with difference between adjacent
// elements as either 0 or 1
import java.util.HashMap;
 
class GFG
{
     
    // function to find maximum length subsequence
    // with difference between adjacent elements as
    // either 0 or 1
    public static int maxLengthSub(int[] arr)
    {
         
        // to store the maximum length subsequence
        int max_val = 0;
        int start = 0;
         
        // 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> map = new HashMap<>();
 
        // traverse the array elements
        for (int i = 0; i < arr.length; i++)
        {
             
            // initialize current length
            // for element arr[i] as 0
            int temp = 0;
            if (map.containsKey(arr[i] - 1))
            {
                temp = map.get(arr[i] - 1);
            }
 
            if (map.containsKey(arr[i]))
            {
                temp = Math.max(temp, map.get(arr[i]));
            }
             
            if (map.containsKey(arr[i] + 1))
            {
                temp = Math.max(temp, map.get(arr[i] + 1));
            }
            temp++;
             
            // update maximum length
            if (temp > max_val)
            {
                max_val = temp;
            }
            map.put(arr[i], temp);
        }
         
        // required maximum length subsequence
        return max_val;
    }
     
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = {2, 5, 6, 3, 7, 6, 5, 8};
        System.out.println(maxLengthSub(arr));
    }
}
 
// This code is contributed
// by tushar jajodia

# Python3 implementation to find maximum
# length subsequence with difference between
# adjacent elements as either 0 or 1
from collections import defaultdict
 
# Function to find maximum length subsequence with
# difference between adjacent elements as either 0 or 1
def maxLenSub(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)
     
    # to store the maximum length subsequence
    maxLen = 0
     
    # traverse the array elements
    for i in range(0, n):
     
        # initialize current length
        # for element arr[i] as 0
        length = 0
         
        # if 'arr[i]-1' is in 'um' and its length of
        # subsequence is greater than 'len'
        if (arr[i]-1) in um and length < um[arr[i]-1]:
            length = um[arr[i]-1]
         
        # if 'arr[i]' is in 'um' and its length of
        # subsequence is greater than 'len'
        if arr[i] in um and length < um[arr[i]]:
            length = um[arr[i]]
             
        # if 'arr[i]+1' is in 'um' and its length of
        # subsequence is greater than 'len'    
        if (arr[i]+1) in um and length < um[arr[i]+1]:
            length = um[arr[i]+1]
         
        # update arr[i] subsequence length in 'um'
        um[arr[i]] = length + 1
         
        # update maximum length
        if maxLen < um[arr[i]]:
            maxLen = um[arr[i]]
     
    # required maximum length subsequence
    return maxLen
 
# Driver program to test above
if __name__ == "__main__":
 
    arr = [2, 5, 6, 3, 7, 6, 5, 8]
    n = len(arr)
    print("Maximum length subsequence =", maxLenSub(arr, n))
     
# This code is contributed by Rituraj Jain

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// function to find maximum length subsequence
// with difference between adjacent elements as
// either 0 or 1
public static int maxLenSub(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 maximum length subsequence
    int maxLen = 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]' is in 'um' and its length of
        // subsequence is greater than 'len'   
        if (um.ContainsKey(arr[i]) && len < um[arr[i]])
            len = um[arr[i]];
             
        // 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 maximum length
        if (maxLen < um[arr[i]])   
            maxLen = um[arr[i]];
    }
      
    // required maximum length subsequence
    return maxLen;       
}
 
// Driver Code
public static void Main()
{
    int[] arr = {2, 5, 6, 3, 7, 6, 5, 8};
    int n = arr.Length;
    Console.WriteLine("Maximum length subsequence = " + maxLenSub(arr, n));
}
}
 
// This code is contributed by sanjoy_62.

<script>
 
// Javascript implementation to find maximum length
// subsequence with difference between adjacent
// elements as either 0 or 1
  
// function to find maximum length subsequence
// with difference between adjacent elements as
// either 0 or 1
function maxLenSub(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
    var um = new Map();
     
    // to store the maximum length subsequence
    var maxLen = 0;
     
    // traverse the array elements
    for (var i=0; i<n; i++)
    {
        // initialize current length
        // for element arr[i] as 0
        var 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]' is in 'um' and its length of
        // subsequence is greater than 'len'   
        if (um.has(arr[i]) && len < um.get(arr[i]))
            len = um.get(arr[i]);
             
        // 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 maximum length
        if (maxLen < um.get(arr[i]))   
            maxLen = um.get(arr[i]);
    }
      
    // required maximum length subsequence
    return maxLen;       
}
  
// Driver program to test above
var arr = [2, 5, 6, 3, 7, 6, 5, 8];
var n = arr.length;
document.write( "Maximum length subsequence = "
     + maxLenSub(arr, n));
 
// This code is contributed by itsok.
</script>

Maximum length subsequence = 5

Complejidad temporal: O(n) 
Espacio auxiliar: O(n)

Gracias a Neeraj por sugerir la solución anterior en los comentarios de esta publicació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.