Dada una array arr[] de tamaño N y un entero K , la tarea es encontrar la subsecuencia más larga tal que la diferencia entre los adyacentes sea K .
Ejemplo:
Entrada: arr[]={1, 2, 3, 4, 5, 3, 2}, K=1
Salida: 6
Explicación: La subsecuencia más larga con la diferencia entre los elementos adyacentes como 1 es: {1, 2, 3 , 4, 3, 2}Entrada: arr[]={1, 2, 3, 2, 3, 7, 2, 1}, K=2
Salida: 3
Enfoque: El problema dado se puede resolver usando Programación Dinámica . La idea es almacenar la longitud de la subsecuencia más larga que tenga una diferencia K entre los adyacentes que termina después de incluir el elemento actual. Cree un mapa desordenado mp donde mp[i] representa la longitud máxima de la subsecuencia que incluye el número entero i .
Entonces, la relación para obtener la subsecuencia de longitud máxima se puede escribir como:
pf[i] = 1 + máx(pf[i – K], pf[i + K])
La cantidad máxima de enteros almacenados en el mapa mp es la respuesta requerida. A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the longest
// subsequence such that difference
// between adjacent elements is K
int longestSubsequence(vector<int>& arr, int K)
{
// Stores length of longest
// subsequence in a map
unordered_map<int, int> mp;
// Variable to store the maximum
// length of subsequence
int mx = 1;
// Loop to iterate through the
// given array
for (auto x : arr) {
mp[x] = 1;
// If (x - K) exists
if (mp.count(x - K)) {
mp[x] = 1 + mp[x - K];
}
// if (x + K) exists
if (mp.count(x + K)) {
mp[x] = max(mp[x], 1 + mp[x + K]);
}
mx = max(mx, mp[x]);
}
// Return Answer
return mx;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 2, 3, 4, 5, 3, 2 };
int K = 1;
cout << longestSubsequence(arr, K);
}
Java
// Java code for the above approach
import java.util.HashMap;
class GFG {
// Function to find the longest
// subsequence such that difference
// between adjacent elements is K
public static int longestSubsequence(int[] arr, int K) {
// Stores length of longest
// subsequence in a map
HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
// Variable to store the maximum
// length of subsequence
int mx = 1;
// Loop to iterate through the
// given array
for (int x : arr) {
mp.put(x, 1);
// If (x - K) exists
if (mp.containsKey(x - K)) {
mp.put(x, 1 + mp.get(x - K));
}
// If (x + K) exists
if (mp.containsKey(x + K)) {
mp.put(x, Math.max(mp.get(x), 1 + mp.get(x + K)));
}
mx = Math.max(mx, mp.get(x));
}
// Return Answer
return mx;
}
// Driver Code
public static void main(String args[]) {
int[] arr = { 1, 2, 3, 4, 5, 3, 2 };
int K = 1;
System.out.print(longestSubsequence(arr, K));
}
}
// This code is contributed by gfgking
Python3
# python code for the above approach
# Function to find the longest
# subsequence such that difference
# between adjacent elements is K
def longestSubsequence(arr, K):
# Stores length of longest
# subsequence in a map
mp = {}
# Variable to store the maximum
# length of subsequence
mx = 1
# Loop to iterate through the
# given array
for x in arr:
mp[x] = 1
# If (x - K) exists
if ((x - K) in mp):
mp[x] = 1 + mp[x - K]
# if (x + K) exists
if ((x+K) in mp):
mp[x] = max(mp[x], 1 + mp[x + K])
mx = max(mx, mp[x])
# Return Answer
return mx
# Driver Code
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5, 3, 2]
K = 1
print(longestSubsequence(arr, K))
# This code is contributed by rakeshsahni
C#
// C# code for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the longest
// subsequence such that difference
// between adjacent elements is K
static int longestSubsequence(List<int> arr, int K)
{
// Stores length of longest
// subsequence in a map
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Variable to store the maximum
// length of subsequence
int mx = 1;
// Loop to iterate through the
// given array
foreach(int x in arr)
{
mp[x] = 1;
// If (x - K) exists
if (mp.ContainsKey(x - K))
{
mp[x] = 1 + mp[x - K];
}
// If (x + K) exists
if (mp.ContainsKey(x + K))
{
mp[x] = Math.Max(mp[x], 1 + mp[x + K]);
}
mx = Math.Max(mx, mp[x]);
}
// Return Answer
return mx;
}
// Driver Code
public static void Main()
{
List<int> arr = new List<int>(){ 1, 2, 3, 4, 5, 3, 2 };
int K = 1;
Console.Write(longestSubsequence(arr, K));
}
}
// This code is contributed by ukasp
Javascript
<script>
// JavaScript code for the above approach
// Function to find the longest
// subsequence such that difference
// between adjacent elements is K
function longestSubsequence(arr, K)
{
// Stores length of longest
// subsequence in a map
let mp = new Map();
// Variable to store the maximum
// length of subsequence
let mx = 1;
// Loop to iterate through the
// given array
for (let x of arr) {
mp.set(x, 1)
// If (x - K) exists
if (mp.has(x - K)) {
mp.set(x, 1 + mp.get(x - K));
}
// if (x + K) exists
if (mp.has(x + K)) {
mp.set(x, 1 + mp.get(x + K));
}
mx = Math.max(mx, mp.get(x));
}
// Return Answer
return mx;
}
// Driver Code
let arr = [1, 2, 3, 4, 5, 3, 2];
let K = 1;
document.write(longestSubsequence(arr, K));
// This code is contributed by Potta Lokesh
</script>
6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vp8602260185 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA