Problem Statement

Given an array A[] of size N, find the longest subsequence such that difference between adjacent elements is one.

Example 1:

Input: N = 7
A[] = {10, 9, 4, 5, 4, 8, 6}
Output: 3
Explaination: The three possible subsequences
{10, 9, 8} , {4, 5, 4} and {4, 5, 6}.

Example 2:

Input: N = 5
A[] = {1, 2, 3, 4, 5}
Output: 5
Explaination: All the elements can be
included in the subsequence.

Problem Link

Longest subsequence-1 | Practice | GeeksforGeeks

Code

lass Solution{
public:
    int longestSubsequence(int N, int A[])
    {
        
        vector<int> dp(N,1);
        
        int largest = 1;
        for(int i=1;i<N;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(abs(A[i]-A[j])==1 and dp[i]<1+dp[j])
                {
                    dp[i] = 1 + dp[j];
                    largest = max(largest,dp[i]);
                }
            }
        }
        
        
        
        return largest;
        
    }
};
        
// Time Complexity : O(n^2)