i know this problem is related with DP. But I am new in DP.
i need a simple editorial for this problem.
please help!
Let dp_{i,j} denote the maximum length of a subsequence such that the xor of the last 2 elements is at most j and the last element is A_i. Now we can deduce that
dp_{i,j} = max(dp_{k,A_i \bigoplus A_k}). There will be at most i different previous xor values, so we can store them all and then sort them. Then we can use prefix maximums and then binary search for the correct index.
We also keep a base case {-1, 1} which means it’s the only element and there is no previous xor value.
See code for more details
1 Like