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.
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"
Este problema se basa en el concepto de problema de subsecuencia creciente más larga .
Let arr[0..n-1] be the input array and
dp[i] be the length of the longest subsequence (with
differences one) ending at index i such that arr[i]
is the last element of the subsequence.
Then, dp[i] can be recursively written as:
dp[i] = 1 + max(dp[j]) where 0 < j < i and
[arr[j] = arr[i] -1 or arr[j] = arr[i] + 1]
dp[i] = 1, if no such j exists.
To find the result for a given array, we need
to return max(dp[i]) where 0 < i < n.
A continuación se muestra una implementación basada en programación dinámica. Sigue la estructura recursiva discutida anteriormente.
C++
// C++ program to find the longest subsequence such
// the difference between adjacent elements of the
// subsequence is one.
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of longest subsequence
int longestSubseqWithDiffOne(int arr[], int n)
{
// Initialize the dp[] array with 1 as a
// single element will be of 1 length
int dp[n];
for (int i = 0; i < n; i++)
dp[i] = 1;
// Start traversing the given array
for (int i = 1; i < n; i++) {
// Compare with all the previous elements
for (int j = 0; j < i; j++) {
// If the element is consecutive then
// consider this subsequence and update
// dp[i] if required.
if ((arr[i] == arr[j] + 1) || (arr[i] == arr[j] - 1))
dp[i] = max(dp[i], dp[j] + 1);
}
}
// Longest length will be the maximum value
// of dp array.
int result = 1;
for (int i = 0; i < n; i++)
if (result < dp[i])
result = dp[i];
return result;
}
// Driver code
int main()
{
// Longest subsequence with one difference is
// {1, 2, 3, 4, 3, 2}
int arr[] = { 1, 2, 3, 4, 5, 3, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << longestSubseqWithDiffOne(arr, n);
return 0;
}
Java
// Java program to find the longest subsequence
// such that the difference between adjacent
// elements of the subsequence is one.
import java.io.*;
class GFG {
// Function to find the length of longest
// subsequence
static int longestSubseqWithDiffOne(int arr[],
int n)
{
// Initialize the dp[] array with 1 as a
// single element will be of 1 length
int dp[] = new int[n];
for (int i = 0; i < n; i++)
dp[i] = 1;
// Start traversing the given array
for (int i = 1; i < n; i++) {
// Compare with all the previous
// elements
for (int j = 0; j < i; j++) {
// If the element is consecutive
// then consider this subsequence
// and update dp[i] if required.
if ((arr[i] == arr[j] + 1) || (arr[i] == arr[j] - 1))
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// Longest length will be the maximum
// value of dp array.
int result = 1;
for (int i = 0; i < n; i++)
if (result < dp[i])
result = dp[i];
return result;
}
// Driver code
public static void main(String[] args)
{
// Longest subsequence with one
// difference is
// {1, 2, 3, 4, 3, 2}
int arr[] = { 1, 2, 3, 4, 5, 3, 2 };
int n = arr.length;
System.out.println(longestSubseqWithDiffOne(
arr, n));
}
}
// This code is contributed by Prerna Saini
Python3
# Function to find the length of longest subsequence
def longestSubseqWithDiffOne(arr, n):
# Initialize the dp[] array with 1 as a
# single element will be of 1 length
dp = [1 for i in range(n)]
# Start traversing the given array
for i in range(n):
# Compare with all the previous elements
for j in range(i):
# If the element is consecutive then
# consider this subsequence and update
# dp[i] if required.
if ((arr[i] == arr[j]+1) or (arr[i] == arr[j]-1)):
dp[i] = max(dp[i], dp[j]+1)
# Longest length will be the maximum value
# of dp array.
result = 1
for i in range(n):
if (result < dp[i]):
result = dp[i]
return result
# Driver code
arr = [1, 2, 3, 4, 5, 3, 2]
# Longest subsequence with one difference is
# {1, 2, 3, 4, 3, 2}
n = len(arr)
print (longestSubseqWithDiffOne(arr, n))
# This code is contributed by Afzal Ansari
C#
// C# program to find the longest subsequence
// such that the difference between adjacent
// elements of the subsequence is one.
using System;
class GFG {
// Function to find the length of longest
// subsequence
static int longestSubseqWithDiffOne(int[] arr,
int n)
{
// Initialize the dp[] array with 1 as a
// single element will be of 1 length
int[] dp = new int[n];
for (int i = 0; i < n; i++)
dp[i] = 1;
// Start traversing the given array
for (int i = 1; i < n; i++) {
// Compare with all the previous
// elements
for (int j = 0; j < i; j++) {
// If the element is consecutive
// then consider this subsequence
// and update dp[i] if required.
if ((arr[i] == arr[j] + 1) || (arr[i] == arr[j] - 1))
dp[i] = Math.Max(dp[i], dp[j] + 1);
}
}
// Longest length will be the maximum
// value of dp array.
int result = 1;
for (int i = 0; i < n; i++)
if (result < dp[i])
result = dp[i];
return result;
}
// Driver code
public static void Main()
{
// Longest subsequence with one
// difference is
// {1, 2, 3, 4, 3, 2}
int[] arr = { 1, 2, 3, 4, 5, 3, 2 };
int n = arr.Length;
Console.Write(
longestSubseqWithDiffOne(arr, n));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find the longest
// subsequence such the difference
// between adjacent elements of the
// subsequence is one.
// Function to find the length of
// longest subsequence
function longestSubseqWithDiffOne($arr, $n)
{
// Initialize the dp[]
// array with 1 as a
// single element will
// be of 1 length
$dp[$n] = 0;
for($i = 0; $i< $n; $i++)
$dp[$i] = 1;
// Start traversing the
// given array
for($i = 1; $i < $n; $i++)
{
// Compare with all the
// previous elements
for($j = 0; $j < $i; $j++)
{
// If the element is
// consecutive then
// consider this
// subsequence and
// update dp[i] if
// required.
if (($arr[$i] == $arr[$j] + 1) ||
($arr[$i] == $arr[$j] - 1))
$dp[$i] = max($dp[$i],
$dp[$j] + 1);
}
}
// Longest length will be
// the maximum value
// of dp array.
$result = 1;
for($i = 0 ; $i < $n ; $i++)
if ($result < $dp[$i])
$result = $dp[$i];
return $result;
}
// Driver code
// Longest subsequence with
// one difference is
// {1, 2, 3, 4, 3, 2}
$arr = array(1, 2, 3, 4, 5, 3, 2);
$n = sizeof($arr);
echo longestSubseqWithDiffOne($arr, $n);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// JavaScript program to find the
// longest subsequence such that the
// difference between adjacent elements
// of the subsequence is one.
// Function to find the length of longest
// subsequence
function longestSubseqWithDiffOne(arr, n)
{
// Initialize the dp[] array with 1 as a
// single element will be of 1 length
let dp = [];
for(let i = 0; i < n; i++)
dp[i] = 1;
// Start traversing the given array
for(let i = 1; i < n; i++)
{
// Compare with all the previous
// elements
for(let j = 0; j < i; j++)
{
// If the element is consecutive
// then consider this subsequence
// and update dp[i] if required.
if ((arr[i] == arr[j] + 1) ||
(arr[i] == arr[j] - 1))
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// Longest length will be the maximum
// value of dp array.
let result = 1;
for(let i = 0; i < n; i++)
if (result < dp[i])
result = dp[i];
return result;
}
// Driver Code
// Longest subsequence with one
// difference is
// {1, 2, 3, 4, 3, 2}
let arr = [1, 2, 3, 4, 5, 3, 2];
let n = arr.length;
document.write(longestSubseqWithDiffOne(arr, n));
// This code is contributed by souravghosh0416
</script>
Producción
6
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n)
Enfoque eficiente
C++
#include<bits/stdc++.h>
using namespace std;
int longestSubsequence(int n, int arr[])
{
if(n==1)
return 1;
unordered_map<int,int> mapp;
int res = 1;
for(int i=0;i<n;i++){
if(mapp.count(arr[i]+1) >0 || mapp.count(arr[i]-1)>0){
mapp[arr[i]]=1+max(mapp[arr[i]+1],mapp[arr[i]-1]);
}
else
mapp[arr[i]]=1;
res = max(res, mapp[arr[i]]);
}
return res;
//This code is contributed by Akansha Mittal
}
int main()
{
// Longest subsequence with one difference is
// {1, 2, 3, 4, 3, 2}
int arr[] = {1, 2, 3, 4, 5, 3, 2};
int n = sizeof(arr)/sizeof(arr[0]);
cout << longestSubsequence(n, arr);
return 0;
}
Java
import java.lang.Math;
import java.util.*;
class GFG {
static int longestSubsequence(int n, int arr[])
{
if (n == 1)
return 1;
Integer dp[] = new Integer[n];
HashMap<Integer, Integer> mapp = new HashMap<>();
dp[0] = 1;
mapp.put(arr[0], 0);
for (int i = 1; i < n; i++) {
if (Math.abs(arr[i] - arr[i - 1]) == 1)
dp[i] = dp[i - 1] + 1;
else {
if (mapp.containsKey(arr[i] + 1)
|| mapp.containsKey(arr[i] - 1)) {
dp[i] = 1
+ Math.max(mapp.getOrDefault(
arr[i] + 1, 0),
mapp.getOrDefault(
arr[i] - 1, 0));
}
else
dp[i] = 1;
}
mapp.put(arr[i], dp[i]);
}
return Collections.max(Arrays.asList(dp));
}
public static void main(String[] args)
{
// Longest subsequence with one
// difference is
// {1, 2, 3, 4, 3, 2}
int arr[] = { 1, 2, 3, 4, 5, 3, 2 };
int n = arr.length;
System.out.println(longestSubsequence(n, arr));
}
}
// This code is contributed by rajsanghavi9.
Python3
def longestSubsequence(A, N):
L = [1]*N
hm = {}
for i in range(1,N):
if abs(A[i]-A[i-1]) == 1:
L[i] = 1 + L[i-1]
elif hm.get(A[i]+1,0) or hm.get(A[i]-1,0):
L[i] = 1+max(hm.get(A[i]+1,0), hm.get(A[i]-1,0))
hm[A[i]] = L[i]
return max(L)
# Driver code
A = [1, 2, 3, 4, 5, 3, 2]
N = len(A)
print(longestSubsequence(A, N))
Producción
6
Complejidad de tiempo : O(n)
Complejidad espacial : O(n)
Este artículo es una contribución de Sahil Chhabra (KILLER) . 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA