问题描述：
一个数组的异或和是指数组中所有的数异或在一起的结果，给定一个数组arr，求最大子数组异或和。
异或运算规则：
异或也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。
异或运算法则为：
a⊕a=0；a⊕b=b⊕a；a⊕b⊕c=a⊕(b⊕c)=(a⊕b)⊕c；
d=a⊕b⊕c可以推出a=d⊕b⊕c；a⊕b⊕a=b。
^也可以表示特殊的二元运算符——逐位逻辑运算符（用于对数据的位进行操作），它表示的含义是逐位异或（xor），要求两个整型操作数。从最小（即最右）的位开始，对操作数逐位操作；如果其中两个数不同则为1，相同则为0。例如：
x → 0000 0000 1011 1111
y → 0000 1111 0101 1111
x^y → 0000 1111 1110 0000
思路：
思路一：查找出数组的全部子数组（时间复杂度为：O(N^2）)，遍历每一个子数组（时间复杂度为：O(N）)，即可查找出最大子数组的异或和。算法的时间复杂度为O(N^3)。
思路二：利用预处理数组求出以每个位置结尾时，从0位置到结尾位置的异或和，由于eor(i) = eor(0~j) ^ eor(j+1~i) --> eor(j+1~i) = eor(0~i) ^ eor(0~j)即可以加速求异或和。我们可以以j位置结尾，0~j,1~j,2~j,...,i~j,分别求出异或和取最大值，每个j位置都求一遍找到最大子数组异或和。算法的时间复杂度为O(N^2)。
思路三： 利用前缀树（把树转化为二进制）。前缀树种有所有从0位置开始到i-1位置的前缀树记录，当要求以i位置结尾时的最大子数组前缀和时，我们不知道前面从哪个位置开始和i位置的数异或起来是最大的，我们可以求出现在从0位置到i位置的异或和，然后在前缀树中利用贪心帮我们找一个最大的前缀和。下面是利用前缀树求的代码。如果最高位是0,那么他希望遇到和他相反的数1,后面的位都希望遇到相反的数，那么该位还是1，如果最高位是1那么希望遇到那么希望遇到1让他最高位变为0成为一个整数，后续希望遇到和他相反的数成为1.时间复杂度O(N)
代码
思路二代码
public static int maxXorSubarray1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int[] eor = new int[arr.length];
eor[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
eor[i] = eor[i - 1] ^ arr[i];
}
int max = Integer.MIN_VALUE;
for (int j = 0; j < arr.length; j++) {
for (int i = 0; i <= j; i++) {
max = Math.max(max, i == 0 ? eor[j] : eor[j] ^ eor[i - 1]);
}
}
return max;
}
思路三代码
public static class Node {
public Node[] nexts = new Node[2];
}
public static class NumTrie {
public Node head = new Node();
//把某个数字newNum加入到这棵树的前缀树中
//num是一个32位的整数，所以加入的过程一共走32步
public void add(int newNum) {
Node cur = head;
for (int move = 31; move >= 0; move--) {
//从高位到低位，取出每一位的状态，如果当前状态是0,path(int) = 0
//如果当前状态是1,path(int) = 1
int path = ((newNum >> move) & 1);
//无路新建，有路复用
cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];
cur = cur.nexts[path];
}
}
//该结构之前收集了一些数字，并且建好了前缀树
//eroi 和 ? ^ 最大结果返回
public int maxXor(int eori) {
Node cur = head;
int res = 0;
for (int move = 31; move >= 0; move--) {
int path = (eori >> move) & 1;
//期待的路
// 若eori是正数，则符号位（最高位）为0，返回结果最大我们就需要一个数的符号位（最高位）也为0
// 若eori是负数，则符号位（最高位）为1，返回结果最大我们就需要一个数的符号位（最高位）也为1
//最高位上我总是期待与你原来的一样
// 我们其他位置上不管正数还是负数我们尽可能保证从高位到低位最多的1
// 正数我们很好理解，负数符号位为1，若其他位置全为1，则这个二进制数字表示-1。（负数十进制变二进制需要取反加一）
//其他位置上我期待与你相反
int best = move == 31 ? path : (path ^ 1);
//实际走的路
//若期待的路存在则有期待的路
//期待的路不存在则走相反的路
best = cur.nexts[best] != null ? best : (best ^ 1);
//(path ^ best ) 当前位位异或完的结果
res |= (path ^ best) << move;
cur = cur.nexts[best];
}
return res;
}
}
public static int maxXorSubarray2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
//0~i 异或和
int eor = 0;
NumTrie numTrie = new NumTrie();
//一个数也没有的时候，异或和是0
numTrie.add(0);
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];// 0...i 异或和
//X 0~0 0~1 ... 0~i1
max = Math.max(max, numTrie.maxXor(eor));
numTrie.add(eor);
}
return max;
}测试代码
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
}
return arr;
}
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int maxSize = 20;
int maxValue = 20;
int testTime = 200000;
System.out.println("测试开始！");
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
int max1 = maxXorSubarray1(arr1);
int max2 = maxXorSubarray2(arr2);
if (max1 != max2) {
System.out.println("出现错误了！");
printArray(arr1);
printArray(arr2);
System.out.println(max1);
System.out.println(max2);
break;
}
}
System.out.println("测试结束！");
}
