Dada una array arr[] de tamaño N y entero K . La tarea es encontrar la subsecuencia más larga con la diferencia entre elementos adyacentes como K
Ejemplos :
Entrada : arr[] = { 5, 5, 5, 10, 8, 6, 12, 13 }, K = 1
Salida : {5, 6}Entrada : arr[] = {4, 6, 7, 8, 9, 8, 12, 14, 17, 15}, K = 2
Salida : {4, 6, 8}
Enfoque : La tarea se puede resolver con la ayuda de la programación dinámica . Cada elemento de la array se puede considerar como el último elemento de una subsecuencia. Para cada elemento, la idea es almacenar la longitud de la subsecuencia más larga que tenga diferencias entre los elementos adyacentes K y el predecesor del elemento actual en esa subsecuencia. Siga los pasos que se mencionan a continuación para implementar el enfoque.
- Cree un mapa, para almacenar la última ocurrencia de cada elemento.
- Cree una array de pares dp[] para almacenar la longitud de la subsecuencia más larga que termina en un índice y el predecesor de ese índice.
- Ahora, recorra la array arr[] , y para cada elemento arr[i] :
- Busque ( arr[i] – K) , ( arr[i] + K) en el mapa.
- Si están presentes, busque la subsecuencia con la longitud máxima y almacene la longitud y el predecesor en dp[i] .
- Imprime la subsecuencia más larga con la ayuda de los predecesores almacenados en la array dp[] .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the longest subsequence
vector<int> maxSubsequence(vector<int>& arr, int K)
{
int N = arr.size();
// Declaring the dp[] array and map
vector<pair<int, int> > dp(N, { 1, -1 });
unordered_map<int, int> mp;
mp[arr[0]] = 1;
// Initialise variable to store
// maximum length and last index of
// the longest subsequence
int maxlen = 1, ind = 0;
// Loop to find out the longest
// subsequence
for (int i = 1; i < N; i++) {
// If arr[i]-K is present in the part
// of array visited till now
if (mp.count(arr[i] - K)) {
dp[i] = { dp[mp[arr[i] - K] - 1].first + 1,
mp[arr[i] - K] - 1 };
}
// If arr[i]+K is present in the part
// of array visited till now
if (mp.count(arr[i] + K)) {
if (dp[i].first
< dp[mp[arr[i] + K] - 1].first + 1) {
dp[i].first
= dp[mp[arr[i] + K] - 1].first + 1;
dp[i].second = mp[arr[i] + K] - 1;
}
}
// If maximum length increase store
// the length and current index as the
// last index of longest subsequence
if (maxlen < dp[i].first) {
maxlen = dp[i].first;
ind = i;
}
mp[arr[i]] = i + 1;
}
// Declare vector to store the
// longest subsequence
vector<int> v;
// Loop to generate the subsequence
while (ind >= 0) {
v.push_back(arr[ind]);
ind = dp[ind].second;
}
reverse(v.begin(), v.end());
return v;
}
// Driver code
int main()
{
vector<int> arr = { 4, 6, 7, 8, 9, 8, 12,
14, 17, 15 };
int K = 2;
// Calling function to find
// longest subsequence
vector<int> longSubseq =
maxSubsequence(arr, K);
for (auto i : longSubseq)
cout << i << " ";
cout << endl;
return 0;
}
Python3
# Python program to implement above approach
# Function to find the longest subsequence
def maxSubsequence(arr, K):
N = len(arr)
# Declaring the dp[] array and map
dp = [[1, -1] for i in range(N)]
mp = {}
mp[arr[0]] = 1
# Initialise variable to store
# maximum length and last index of
# the longest subsequence
maxlen = 1
ind = 0
# Loop to find out the longest
# subsequence
for i in range(1,N):
# If arr[i]-K is present in the part
# of array visited till now
if (arr[i] - K) in mp:
dp[i] = [dp[mp[arr[i] - K] - 1][0] + 1, mp[arr[i] - K] - 1]
# If arr[i]+K is present in the part
# of array visited till now
if (arr[i] + K) in mp:
if (dp[i][0] < dp[mp[arr[i] + K] - 1][0] + 1):
dp[i][0]= dp[mp[arr[i] + K] - 1][0] + 1
dp[i][1] = mp[arr[i] + K] - 1
# If maximum length increase store
# the length and current index as the
# last index of longest subsequence
if (maxlen < dp[i][0]):
maxlen = dp[i][0]
ind = i
mp[arr[i]] = i + 1
# Declare vector to store the
# longest subsequence
v =[]
# Loop to generate the subsequence
while (ind >= 0):
v.append(arr[ind])
ind = dp[ind][1]
v.reverse()
return v
# Driver code
arr = [4, 6, 7, 8, 9, 8, 12, 14, 17, 15 ]
K = 2
# Calling function to find
# longest subsequence
longSubseq = maxSubsequence(arr, K)
for i in longSubseq:
print(i , end= " ")
print()
# This code is contributed by Shubham Singh
Javascript
<script>
// JavaScript program to implement above approach
// Function to find the longest subsequence
function maxSubsequence(arr, K){
let N = arr.length
// Declaring the dp[] array and map
let dp = new Array(N).fill([]).map(()=>[1,-1])
let mp = new Map()
mp.set(arr[0], 1)
// Initialise variable to store
// maximum length and last index of
// the longest subsequence
let maxlen = 1
let ind = 0
// Loop to find out the longest
// subsequence
for(let i=1;i<N;i++){
// If arr[i]-K is present in the part
// of array visited till now
if(mp.has(arr[i] - K)== true)
dp[i] = [dp[mp.get(arr[i] - K) - 1][0] + 1, mp.get(arr[i] - K) - 1]
// If arr[i]+K is present in the part
// of array visited till now
if(mp.has(arr[i] + K)){
if (dp[i][0] < dp[mp.get(arr[i] + K) - 1][0] + 1){
dp[i][0]= dp[mp.get(arr[i] + K) - 1][0] + 1
dp[i][1] = mp.get(arr[i] + K) - 1
}
}
// If maximum length increase store
// the length and current index as the
// last index of longest subsequence
if (maxlen < dp[i][0]){
maxlen = dp[i][0]
ind = i
}
mp.set(arr[i], i + 1)
}
// Declare vector to store the
// longest subsequence
let v =[]
// Loop to generate the subsequence
while (ind >= 0){
v.push(arr[ind])
ind = dp[ind][1]
}
v.reverse()
return v
}
// Driver code
let arr = [4, 6, 7, 8, 9, 8, 12, 14, 17, 15 ]
let K = 2
// Calling function to find
// longest subsequence
let longSubseq = maxSubsequence(arr, K)
for(let i of longSubseq)
document.write(i ," ")
document.write("</br>")
// This code is contributed by shinjanpatra
</script>
Producción
4 6 8
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)