Longest subsequence such that difference between adjacents is one

The problem “Longest subsequence such that difference between adjacents is one” states that you are given an integer array. Now you need to find the length of longest subsequence such that the difference of adjacent elements is 1.

Example

1 2 3 4 7 5 9 4

6

Explanation

As we can see that there are two subsequences that follow the condition. They are {1, 2, 3, 4, 5, 4} and the other one is {7, 8}. So the longest subsequence is the first one. Thus the answer is 6.

Approach for Longest subsequence such that difference between adjacents is one

A naive approach would be the generation of such possible subsequences. But we know that generation of subsequences is a very time-consuming task. Since it will require recursion and is of exponential time complexity. So to solve the problem, we require a better approach. A better approach would be dynamic programming. Because the problem is similar to that of the Longest Increasing Subsequence. In this problem, we need to find the longest subsequence whose adjacent elements should have a difference of 1. So, to solve the problem we start traversing over the elements of the input array.

Before traversing we set our base case which is our first element. We can always create a subsequence of length 1. If we choose a single element. Now as we move forward, we will keep on checking in a backward direction that if we somehow find an element that has an absolute difference of 1 with the current element. Then we can simply add the current element to the subsequence which had the other element as its last element. And as we find such an element we keep on updating the maximum length for our subsequence ending at the current element. And after computing all these values, we find the maximum of all these values. That is the answer to our problem.

Code

C++ code for Longest subsequence such that difference between adjacents is one

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
    int n = (sizeof input)/(sizeof input[0]);
    int dp[n];memset(dp, 0, sizeof dp);
    dp[0] = 1;
    for(int i=1;i<n;i++){
        for(int j=i;j>=0;j--)
            if(abs(input[i]-input[j]) == 1)
                dp[i] = max(dp[i], dp[j]+1);
    }
    int answer = 0;
    for(int i=0;i<n;i++)
        answer = max(answer, dp[i]);
    cout<<answer;
}

6

Java code for Longest subsequence such that difference between adjacents is one

import java.util.*;

class Main{
  public static void main(String[] args){
      int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
      int n = input.length;
      int dp[] = new int[n];
      for(int i=1;i<n;i++)dp[i] = 0;

      dp[0] = 1;
      for(int i=1;i<n;i++){
          for(int j=i;j>=0;j--)
              if(Math.abs(input[i]-input[j]) == 1)
                  dp[i] = Math.max(dp[i], dp[j]+1);
      }
      int answer = 0;
      for(int i=0;i<n;i++)
          answer = Math.max(answer, dp[i]);
      System.out.print(answer);
  }
}

6

Complexity Analysis

Time Complexity

O(N^2), because we had two loops. One was simply traversing over all the elements and the other one is traversing over all the elements which have been traversed. Thus the time complexity for the algorithm becomes polynomial.

Space Complexity

O(N), since we had to store the result for all the elements which we had traversed until now. Thus the space complexity is linear.