Length of the longest subsequence such that xor of adjacent elements is non | C ++ implementation of the approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int LongestXorSubsequence ( int arr [ ] , int n ) { vector < pair < int , pair < int , int > > > v ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { v . push_back ( make_pair ( arr [ i ] ^ arr [ j ] , make_pair ( i , j ) ) ) ; } } sort ( v . begin ( ) , v . end ( ) ) ; int dp [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { dp [ i ] = 1 ; } for ( auto i : v ) { dp [ i . second . second ] = max ( dp [ i . second . second ] , 1 + dp [ i . second . first ] ) ; } int ans = 1 ; for ( int i = 0 ; i < n ; i ++ ) ans = max ( ans , dp [ i ] ) ; return ans ; } int main ( ) { int arr [ ] = { 2 , 12 , 6 , 7 , 13 , 14 , 8 , 6 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << LongestXorSubsequence ( arr , n ) ; return 0 ; }