Length of the longest subsequence such that xor of adjacent elements is non | Function to find the length of the longest subsequence such that the XOR of adjacent elements in the subsequence must be non - decreasing ; Computing xor of all the pairs of elements and store them along with the pair ( i , j ) ; Sort all possible xor values ; Initialize the dp array ; Calculating the dp array for each possible position and calculating the max length that ends at a particular index ; Taking maximum of all position ; Driver code
def LongestXorSubsequence ( arr , n ) : NEW_LINE INDENT v = [ ] NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT for j in range ( i + 1 , n ) : NEW_LINE INDENT v . append ( [ ( arr [ i ] ^ arr [ j ] ) , ( i , j ) ] ) NEW_LINE DEDENT DEDENT v . sort ( ) NEW_LINE dp = [ 1 for x in range ( 88 ) ] NEW_LINE for a , b in v : NEW_LINE INDENT dp [ b [ 1 ] ] = max ( dp [ b [ 1 ] ] , 1 + dp [ b [ 0 ] ] ) NEW_LINE DEDENT ans = 1 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT ans = max ( ans , dp [ i ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ 2 , 12 , 6 , 7 , 13 , 14 , 8 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE print ( LongestXorSubsequence ( arr , n ) ) NEW_LINE