# Longest subsequence such that difference between adjacents is one

Given an array of n size, the task is to find the longest subsequence such that difference between adjacents is one.

Examples:

```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"
```

This problem is based upon the concept of Longest Increasing Subsequence Problem.

```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.
```

Following is a Dynamic Programming based implementation. It follows the recursive structure discussed above.

## C++

 `// C++ program to find the longest subsequence such ` `// the difference between adjacent elements of the ` `// subsequence is one. ` `#include ` `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

/div>

## 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 `

## Python

 `# 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

 ` `

Output:

```6
```

Time Complexity: O(n2)
Auxiliary Space: O(n)

## tags:

Dynamic Programming LIS Dynamic Programming