Maximum XOR of Subsequences - Solution & Explanation

Problem Overview: You are given an integer array and must choose any subsequence whose XOR value is as large as possible. The task is to determine the maximum XOR achievable by selecting any subset of elements while preserving their order.

Approach 1: Brute Force Subsequence Enumeration (O(2^n) time, O(1) space)

The most direct method is to try every possible subsequence. For each subset of indices, compute the XOR of the selected numbers and track the maximum value. This works because XOR is associative and easy to compute incrementally. However, the number of subsequences is 2^n, which becomes infeasible once n grows beyond ~25. This approach is useful only for understanding the problem or verifying small test cases.

Approach 2: Dynamic Programming on XOR States (O(n * M) time, O(M) space)

Another idea is to track all reachable XOR values while iterating through the array. Maintain a set or boolean DP array where each state represents a possible XOR result. For every number x, update the states by inserting state ^ x. This effectively simulates choosing or skipping each element. The limitation is that the number of XOR states can grow up to the maximum value range (M), which becomes large when integers have many bits. This approach works when values are small but struggles with typical competitive programming constraints.

Approach 3: Greedy XOR Linear Basis (O(n * B) time, O(B) space)

The optimal strategy treats the problem as a maximum subset XOR problem using a linear basis over bits. Iterate through the array and maintain a basis where each element represents a number with a unique highest set bit. For every new value, reduce it using existing basis vectors (XOR with them if it lowers the value). If the result is non-zero, insert it into the basis. This effectively performs Gaussian elimination in binary space.

Once the basis is built, compute the maximum XOR by greedily combining basis elements from highest bit to lowest. Each step attempts ans = max(ans, ans ^ basis[i]). The basis guarantees independence between vectors, allowing you to construct the maximum possible XOR value.

This method relies heavily on Bit Manipulation and a greedy property of XOR linear independence. It is widely used in problems involving maximum subset XOR and XOR optimization on Array data. The elimination process is conceptually similar to techniques used in Math problems involving binary vector spaces.

Recommended for interviews: The XOR linear basis approach is the expected solution. Brute force shows you understand subsequences and XOR behavior, but the greedy basis demonstrates deeper knowledge of bit manipulation and linear independence—something interviewers often look for in hard problems.