1. Given an array of n integers, find the maximum length of the subsequence with difference between adjacent elements as either a 0 or 1.
Input: arr[] = {2,5,6,3,7,6,5,8}
Output: 5
The subsequence is {5,6,7,6,5}
Input: arr[] = {-2,-1,5,-1,4,0,3}
Output: 4
The subsequence is {-2,-1,-1,0}

First you have to check whether the absolute differences between the adjacent elements of the subsequences is either 0 or 1. 

# Python implementation to find the maximum length sequences with 
# difference between the adjacent elements as either 0 or 1
# Function to find the maximum length subsequence with difference
# between the adjacent elements as either 0 or 1
def maxLengthSubsq(arr, n):
    mls=[]
    max=0
# Initialize mls[] values for all indexes
    for i in range(n):
        mls.append(1)
# Compute the optimized maximum length subsequence values in bottom
# up manner
    for i in range(n):
        for j in range(i):
            if (abs(arr[i]-arr[j]<=1 and mls[i]<mls[j]+1)
                mls[i]=mls[j]+1
# Required maximum length subsequence
    return max
# Driver program to test the above function
arr=[2,5,6,3,7,6,5,8]
n=len(arr)
print("Maximum length subsequence=",maxLengthSubsq(arr,n))

Output:

Maximum length subsequence = 5

The time complexity: O(n)2

The Auxiliary space: O(n)

If you have any question or comment, do not hesitate to ask us.

Quote: The moon looks upon many night flowers; the night flowers see but one moon. – Jean Ingelow

Advertisement