Given an array of integers and an integer k, determine the length of the longest valid subsequence in the array.
A subsequence is formed by removing zero or more elements from the array without changing the order of the remaining elements. In a valid subsequence, each pair of adjacent elements has bitwise XOR equal to k.
Note that any subsequence of length 1 is valid regardless of the value of k, because there is no pair of adjacent elements in such a subsequence.
Example
n = 5
arr = [2, 1, 3, 5, 2]
k = 2The subsequence [1, 3] is valid because for its adjacent pair we have 1 XOR 3 = 2. There are no other valid subsequences longer than 2. For example, [2, 1, 3] is not valid because 2 XOR 1 != 2.
Function Description
Complete the function maxSubsequenceLength in the editor below.
The function must return the length of the longest valid subsequence of the array, given parameter k.
Parameters
INTEGER n: the size ofarrINTEGER kINTEGER_ARRAY arr
这题要求在保持相对顺序不变的前提下，找出最长的子序列，使得相邻两个元素的按位异或都等于 k。核心做法是用哈希表或数组做动态规划：遍历数组时，设以当前值结尾的最长合法长度为 dp[x]，它可以由之前是否出现过值 x XOR k 转移而来，因此每个元素只需 O(1) 时间更新。由于数值范围较大，若值域已知且不超界可以用数组，否则用哈希表记录“某个值结尾的最佳长度”。本质上这是一个基于值状态转移的最长链问题，答案是所有 dp 状态中的最大值；如果没有可衔接的前驱，单个元素本身也能构成长度 1 的合法子序列。
