子数组的最大异或和问题
作者：Grey
原文地址：
题目描述
数组中所有数都异或起来的结果，叫做异或和。给定一个数组 arr，其中可能有正、有负，有零，返回 arr 的最大子数组异或和
题目链接见：牛客-子数组的最大异或和
暴力解
枚举每个子数组的异或和，抓取全局最大值返回，整个算法时间复杂度\(O(N^3)\)，整个过程比较简单，不赘述，基于这个暴力解法，可以有优化一些的算法，就是利用前缀异或和数组，时间复杂度可以减少到\(O(N^2)\)，思路如下
第一步
申请一个和原始数组一样长的前缀异或和数组
int[] eor = new int[arr.length];
其中eor[i]表示原始数组 0 位置到 i 位置的异或和是多少，实现代码如下：
eor[0] = arr[0];
for (int i = 1; i < n; i++) {
eor[i] = eor[i - 1] ^ arr[i];
}
有了 eor 数组以后，对于任意 i 位置，0 到 i 区间的异或和就可以直接获取到了，接下来是枚举数组中任意两个位置 i 和 j 区间的异或和，由于
i ~ j 之间的异或和等于 eor[j] ^ eor[i-1](i > 0)，所以
任何两个位置之间的异或和信息可以通过如下代码求得，其中 max 是全局异或和的最大值
for (int i = 1; i < n; i++) {
max = Math.max(max, eor[i]);
for (int j = i; j < n; j++) {
max = Math.max(max, eor[j] ^ eor[i - 1]);
}
}
完整代码如下
public static int maxEor1(int[] arr, int n) {
int[] eor = new int[arr.length];
int max = arr[0];
eor[0] = arr[0];
for (int i = 1; i < n; i++) {
eor[i] = eor[i - 1] ^ arr[i];
}
for (int i = 1; i < n; i++) {
max = Math.max(max, eor[i]);
for (int j = i; j < n; j++) {
max = Math.max(max, eor[j] ^ eor[i - 1]);
}
}
return max;
}
整个算法复杂度是\(O(N^2)\)，并不是最优解。
最优解
根据上述暴力解法，时间复杂度比较高的部分是：
当确定了 0 ~ i 位置的异或和以后，如何定位 0 ~ j 这个区间，使得 j ~ i 之间的异或和最大。
暴力解法使用的是遍历的方式，而最优解，可以使用前缀树进行加速匹配，关于前缀树的内容，可以参考：前缀树的设计和实现
以数组[11,1,15,10,13,4]为例，我们把其前缀异或和数组转换成二进制，结果如下(其中eor[i..j]表示i~j的异或和)
eor[0..0] = 1011
eor[0..1] = 1010
eor[0..2] = 0101
eor[0..3] = 1111
eor[0..4] = 0010
eor[0..5] = 0110
把这些前缀异或和加入前缀树,
接下来，对于任何一个eor[i](0~i的异或和)来说，进入前缀树以后，前缀树需要快速找到和其匹配的eor[j]，使得i~j之间的异或和最大，规则就是最高位（符号位）期待一样，紧着高位要期待不一样的值
例如：
eor[2] = 0101
eor[2] 期待和它符号位一样为0的值，紧着高位（由于前面28都是0，所以不存在和它符号不一样的，只看最后4位，
通过这个贪心，就可以在\(O(1)\)时间复杂度直接得到结果。
说明：如果期待遇到 0 可是前缀树没有往 0 方向的路，那直接返回 1 即可，反之亦然。
完整代码如下
public static int maxEor(int[] arr, int n) {
int[] eor = new int[arr.length];
int max = 0;
eor[0] = arr[0];
for (int i = 1; i < n; i++) {
eor[i] = eor[i - 1] ^ arr[i];
}
Trie trie = new Trie(eor);
trie.add(eor[0]);
for (int i = 1; i < n; i++) {
max = Math.max(max, trie.get(eor[i]));
}
return max;
}
public static class Trie {
public Node head;
public Trie(int[] arr) {
head = new Node();
for (int eor : arr) {
add(eor);
}
}
public void add(int num) {
Node cur = head;
for (int bit = 31; bit >= 0; bit--) {
int i = ((num >>> bit) & 1);
if (cur.next[i] == null) {
cur.next[i] = new Node();
}
cur = cur.next[i];
}
}
public int get(int eor) {
int expect = 0;
Node cur = head;
for (int bit = 31; bit >= 0; bit--) {
// 符号位期待一样的
// 非符号位期待相反的
int expectBit = bit == 31 ? ((eor >>> bit) & 1) : (eor >>> bit & 1 ^ 1);
if (cur.next[expectBit] != null) {
expect = ((expectBit << bit) | expect);
cur = cur.next[expectBit];
} else {
expectBit = (expectBit ^ 1);
cur = cur.next[expectBit];
expect = ((expectBit << bit) | expect);
}
}
return expect ^ eor;
}
}
public static class Node {
public Node[] next = new Node[2];
}
整个算法时间复杂度\(O(N)\)，最优解。