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
function LongestXorSubsequence ( arr , n ) { let v = [ ] ; for ( let i = 0 ; i < n ; i ++ ) { for ( let j = i + 1 ; j < n ; j ++ ) { v . push ( [ arr [ i ] ^ arr [ j ] , [ i , j ] ] ) ; } } v . sort ( ( a , b ) => a [ 0 ] - b [ 0 ] ) ; let dp = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { dp [ i ] = 1 ; } for ( let i of v ) { dp [ i [ 1 ] [ 1 ] ] = Math . max ( dp [ i [ 1 ] [ 1 ] ] , 1 + dp [ i [ 1 ] [ 0 ] ] ) ; } let ans = 1 ; for ( let i = 0 ; i < n ; i ++ ) ans = Math . max ( ans , dp [ i ] ) ; return ans ; } let arr = [ 2 , 12 , 6 , 7 , 13 , 14 , 8 , 6 ] ; let n = arr . length ; document . write ( LongestXorSubsequence ( arr , n ) ) ;