直接说这道题时间复杂度O(n)的做法,构建前缀树.假设将0-0,0-1,0-2,...,0-i-1的异或结果全部装在前缀树中,那么以i结尾的最大异或和就是0到某一位置x的异或结果和i异或结果最大,举个例子,假设x是3,0-3的异或结果和i进行异或得到的结果最大,那么就说明4-i的异或结果是最大的.
但是如何知道x到底是多少,换句话说,0-x中哪个值和i进行异或得到的结果最大.其实这个也比较好想,假设i是0100(最高位0是符号位),只需要沿着前缀树找到0011,异或出来的结果就是0111,一定就是最大的,如果不能刚好找到合适的,那就有什么选什么,只要保证从最高位开始往下每次的决策是最优的就行
有一种特殊情况,假设i还是0100,但是此时前缀树中最高位只有1,没有0,那么最高位得出的异或结果永远是负数,后面的位应该如何选?其实也是按照最优决策去选,假设异或结果是1111,那么转换为十进制就是-1,绝对没有比这还大的负数了