I was trying to solve this problem from cses that is the maximum xor of a subarray of a given array. Can someone please help me to solve it. I tried for sometime but could not find any way.
This is the problem : Max Xor Subarray
Also it will be very helpful if you could give hints on solving the maximum Xor of subset of an array which i think is somewhat similar to the first problem. This one : Max Xor Subset
Thanks in advance.
First one using binary trie.
Second one using xor basis.
The maximum XOR subarray can be converted into the XOR of the maximum two XOR prefix sums, which can then be easily solved using 01-trie.
The maximum XOR subsets can be queried directly by inserting them into a linear basis.
Thanks a lot man. Time to learn something new :D
Definitely not recommended to learn these at this stage.
The two comments above me are literally giving the same, correct answer. Yet there's somehow a huge disparity in upvotes / downvotes. Make it make sense pls
I think that you can use a slightly modified Kadane's algorithm. Instead of summing the values in the array, you just xor them.
GPT comment. This obviously doesn't work.
This works if the problem is best prefix, but fails in cases such as this
[2, 2, 1]
Optimal is 3 (sub array from indices 1 to 2), but your code outputs 2.