Longest subsequence -1, LIS -1

 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[] = {11, 10, 4, 5, 4, 9, 6}
Output: 3
Explaination: The three possible subsequences 
{11, 10, 9} , {4, 5, 4} and {4, 5, 6}.

Solution - 

Follow LIS, it is same.

class Solution{

public:

    int longestSubsequence(int N, int A[])

    {

        // code here

        vector<int> dp(N, 1);

        if(N < 1) return 0;

        for(int i = 1; i < N; i++)

        {

            for(int j = 0; j < i; j++)

            {

                if(abs(A[i] - A[j]) == 1)

                dp[i] = max(dp[i], dp[j] + 1);

            }

        }

        int ans = 0;

        for(auto a : dp)

        ans = max(a, ans);        

        return ans;

    }

};