Subsecuencia más larga que tiene una diferencia entre el elemento máximo y mínimo igual a K

Dada una array arr[] que consiste en N enteros y un entero K , la tarea es encontrar la subsecuencia más larga de la array dada tal que la diferencia entre el elemento máximo y mínimo en la subsecuencia sea exactamente K .

Ejemplos:

Entrada: arr[] = {1, 3, 2, 2, 5, 2, 3, 7}, K = 1
Salida: 5
Explicación:
La subsecuencia más larga cuya diferencia entre el elemento máximo y mínimo es K(= 1) es {3, 2, 2, 2, 3}.
Por lo tanto, la longitud es 5.

Entrada: arr [] = {4, 3, 3, 4}, K = 4
Salida: 0

Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias posibles de la array dada y, para cada subsecuencia, encontrar la diferencia entre los valores máximo y mínimo en la subsecuencia. Si es igual a K , actualice la longitud de subsecuencia más larga resultante. Después de verificar todas las subsecuencias, imprima la longitud máxima obtenida.

Complejidad temporal: O(2 ^N )
Espacio auxiliar: O(1)

Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en la observación de que en la subsecuencia requerida, solo pueden estar presentes dos elementos únicos, y su diferencia debe ser K . El problema se puede resolver mediante Hashing , para almacenar la frecuencia de cada elemento de la array . Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos ans , para almacenar la longitud de la subsecuencia más larga.
• Inicialice un hashmap , digamos M , que almacene la frecuencia de los elementos del arreglo .
• Recorra la array arr[] usando la variable i y para cada elemento de la array arr[i] , incremente la frecuencia de arr[] en M en 1 .
• Ahora recorra el hashmap M y para cada clave (digamos X ) en M , si (X + K) también está presente en M , luego actualice el valor de ans al máximo de ans y la suma del valor de ambas claves .
• Después de completar los pasos anteriores, imprima el valor de ans como resultado.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find longest subsequence
// having absolute difference between
// maximum and minimum element K
void longestSubsequenceLength(int arr[],
                              int N, int K)
{
    // Stores the frequency of each
    // array element
    unordered_map<int, int> um;
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++)
 
        // Increment um[arr[i]] by 1
        um[arr[i]]++;
 
    // Store the required answer
    int ans = 0;
 
    // Traverse the hashmap
    for (auto it : um) {
 
        // Check if it.first + K
        // exists in the hashmap
        if (um.find(it.first + K)
            != um.end()) {
 
            // Update the answer
            ans = max(ans,
                      it.second
                          + um[it.first + K]);
        }
    }
 
    // Print the result
    cout << ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 3, 2, 2, 5, 2, 3, 7 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 1;
 
    longestSubsequenceLength(arr, N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
  
// Function to find longest subsequence
// having absolute difference between
// maximum and minimum element K
static void longestSubsequenceLength(int []arr,
                                     int N, int K)
{
     
    // Stores the frequency of each
    // array element
    Map<Integer,
        Integer> um = new HashMap<Integer,
                                  Integer>();
 
    // Traverse the array arr[]
    for(int i = 0; i < N; i++)
    {
        if (um.containsKey(arr[i]))
            um.put(arr[i], um.get(arr[i]) + 1);
        else
            um.put(arr[i], 1);
    }
     
    // Store the required answer
    int ans = 0;
 
    // Traverse the hashmap
    for(Map.Entry<Integer, Integer> e : um.entrySet())
    {
         
        // Check if it.first + K
        // exists in the hashmap
        if (um.containsKey(e.getKey() + K))
        {
             
            // Update the answer
            ans = Math.max(ans, e.getValue() +
                           um.get(e.getKey() + K));
        }
    }
 
    // Print the result
    System.out.println(ans);
}
 
// Driver Code
public static void main(String args[])
{
    int []arr = { 1, 3, 2, 2, 5, 2, 3, 7 };
    int N = arr.length;
    int K = 1;
     
    longestSubsequenceLength(arr, N, K);
}
}
 
// This code is contributed by bgangwar59

# Python3 program for the above approach
from collections import defaultdict
 
# Function to find longest subsequence
# having absolute difference between
# maximum and minimum element K
def longestSubsequenceLength(arr, N, K):
 
    # Stores the frequency of each
    # array element
    um = defaultdict(int)
 
    # Traverse the array arr[]
    for i in range(N):
 
        # Increment um[arr[i]] by 1
        um[arr[i]] += 1
 
    # Store the required answer
    ans = 0
 
    # Traverse the hashmap
    for it in um.keys():
 
        # Check if it.first + K
        # exists in the hashmap
        if (it + K) in um:
 
            # Update the answer
            ans = max(ans,
                      um[it]
                      + um[it + K])
 
    # Print the result
    print(ans)
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 3, 2, 2, 5, 2, 3, 7]
    N = len(arr)
    K = 1
 
    longestSubsequenceLength(arr, N, K)
 
    # This code is contributed by chitranayal.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
 
// Function to find longest subsequence
// having absolute difference between
// maximum and minimum element K
static void longestSubsequenceLength(int[] arr,
                              int N, int K)
{
   
    // Stores the frequency of each
    // array element
    Dictionary<int, int> um = new Dictionary<int, int>();
 
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
          
        // Increase the counter of
        // the array element by 1
        int count = um.ContainsKey(arr[i]) ? um[arr[i]] : 0;
        if (count == 0)
        {
            um.Add(arr[i], 1);
        }
        else
        {
            um[arr[i]] = count + 1;
        }
    }
 
    // Store the required answer
    int ans = 0;
 
    // Traverse the hashmap
    foreach(KeyValuePair<int, int> it in um)
    {
 
        // Check if it.first + K
        // exists in the hashmap
        if (um.ContainsKey(it.Key + K))
        {
 
            // Update the answer
            ans = Math.Max(ans, (it.Value + um[it.Key + K]));
        }
    }
 
    // Print the result
    Console.Write(ans);
}
 
// Driver Code
public static void Main()
{
    int[] arr = { 1, 3, 2, 2, 5, 2, 3, 7 };
    int N = arr.Length;
    int K = 1;
 
    longestSubsequenceLength(arr, N, K);
}
}
 
// This code is contributed by splevel62.

<script>
 
// Javascript program for the above approach
 
// Function to find longest subsequence
// having absolute difference between
// maximum and minimum element K
function longestSubsequenceLength(arr, N, K)
{
    // Stores the frequency of each
    // array element
    var um = new Map();
 
    // Traverse the array arr[]
    for (var i = 0; i < N; i++)
 
        // Increment um[arr[i]] by 1
        if(um.has(arr[i]))
        {
            um.set(arr[i], um.get(arr[i])+1);
        }
        else
        {
            um.set(arr[i], 1);
        }
 
    // Store the required answer
    var ans = 0;
 
    // Traverse the hashmap
    um.forEach((value, key) => {
          
        // Check if it.first + K
        // exists in the hashmap
        if (um.has(key+K)) {
 
            // Update the answer
            ans = Math.max(ans,
                      value
                          + um.get(key+K));
        }
    });
 
    // Print the result
    document.write( ans);
}
 
// Driver Code
var arr = [ 1, 3, 2, 2, 5, 2, 3, 7 ];
var N = arr.length;
var K = 1;
longestSubsequenceLength(arr, N, K);
 
</script>

5

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