Longest Subsequence With Difference One

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
12 upvotes
Asked in companies
HSBCAmazonCIS - Cyber Infrastructure

Problem statement

You are given an array “nums” of size N. Your task is to find the length of the longest subsequence of array “nums” such that the absolute difference between every adjacent element in the subsequence is one.

For Example: 
If “nums” = {2, 1, 3}.

The valid non-empty subsequences of the array are {2}, {1}, {3}, {2, 1}, {1, 3}, {2, 3} and {2, 1, 3}. So, the longest subsequence satisfying the given conditions are {2, 1} and {2, 3}. The length of the longest subsequence is 2. So, the answer is 2.

The subsequence of an array is a sequence of numbers that can be formed by deleting some or no elements without changing the order of the remaining elements. For example, if the given array “nums” = {1, 2, 5, 4, 8}, then {1, 2, 5, 4, 8}, {1, 5, 8}, {2} are some of the valid subsequences whereas the sequence {4, 2} is not a valid subsequence as the order of the elements differ from the original array.

Note: 
Any subsequence of length = 1 is also a valid subsequence.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains an integer ‘T', which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case contains a single integer N, denoting the size of the array “nums”.
The second line of each test case contains N space-separated integers denoting the elements of the array “nums”.
Output format: 
For each test case, print the length of the longest subsequence of array “nums” such that the difference between adjacent elements is one.

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 5000
-10^9 <= nums[i] <= 10^9

Time limit: 1 second
Sample Input 1:
2
5
4 2 1 5 6
6
-2 2 -1 1 0 -1
Sample Output 1:
3
4
Explanation For Sample Input 1:
For the first test case, the longest subsequence satisfying the condition is {4, 5, 6}.

For the second test case, the longest subsequence satisfying the condition is {-2, -1, 0, -1}. There is another possible subsequence of the same length, i.e., {2, 1, 0, -1}. The length of both the subsequences is 4.
Sample Input 2:
2
4
5 6 5 6
1
8
Sample Output 2:
4
1
Hint

Think of a Dynamic Programming approach similar to LIS.

Approaches (2)
Dynamic-Programming

The idea is similar to the LIS problem. We create a dp array of size N and initialize all the elements to 1. We run a loop from i = 0 to N - 1 and for each element, we run another loop from j = i + 1 to N. If the absolute difference between nums[i] and nums[j] is 1, then store the maximum of dp[j] and dp[i] + 1 in dp[j].

 

Steps:

 

  • Create a dp array of size N and initialize all the elements to 1.
  • Run a loop from i = 0 to N - 1 and do:
    • Run a loop from j = i + 1 to N and do:
      • If abs(nums[j] - nums[i]) == 1, then dp[j] = max(dp[j], dp[i] + 1).
  • Create a variable maximum to store the length of the longest subsequence satisfying the condition. Initialize it to 0.
  • Run a loop from i = 0 to N and do:
    • Make maximum = max(maximum, dp[i]).
  • Finally, return the maximum.
Time Complexity

O(N ^ 2), where N is the size of the array “nums”.

 

Since there are two nested for loops, hence the time complexity is O(N^2).

Space Complexity

O(N), where N is the size of the array “nums”.

 

The space complexity due to the ‘dp’ array is O(N).

Code Solution
(100% EXP penalty)
Longest Subsequence With Difference One
Full screen
Console