数组中所有数都异或起来的结果，叫做异或和。给定一个数组arr，返回arr的最大子数组异或和。
前缀树。一个数，用二进制表示，0走左边分支，1走右边分支。
时间复杂度：O(N)。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
arr := []int{-1, 2}
ret := maxXorSubarray2(arr)
fmt.Println(ret)
}
// 前缀树的Node结构
// nexts[0] -> 0方向的路
// nexts[1] -> 1方向的路
// nexts[0] == null 0方向上没路！
// nexts[0] != null 0方向有路，可以跳下一个节点
// nexts[1] == null 1方向上没路！
// nexts[1] != null 1方向有路，可以跳下一个节点
type Node struct {
nexts []*Node
}
func twoSelectOne(condition bool, a int, b int) int {
if condition {
return a
} else {
return b
}
}
func NewNode() *Node {
ret := &Node{}
ret.nexts = make([]*Node, 2)
return ret
}
// 基于本题，定制前缀树的实现
type NumTrie struct {
// 头节点
head *Node
}
func NewNumTrie() *NumTrie {
ret := &NumTrie{}
ret.head = NewNode()
return ret
}
func (this *NumTrie) add(newNum int) {
cur := this.head
for move := 63; move >= 0; move-- {
path := (newNum >> move) & 1
if cur.nexts[path] == nil {
cur.nexts[path] = NewNode()
}
cur = cur.nexts[path]
}
}
// 该结构之前收集了一票数字，并且建好了前缀树
// num和 谁 ^ 最大的结果（把结果返回）
func (this *NumTrie) maxXor(num int) int {
cur := this.head
ans := 0
for move := 63; move >= 0; move-- {
// 取出num中第move位的状态，path只有两种值0就1，整数
path := (num >> move) & 1
// 期待遇到的东西
best := twoSelectOne(move == 63, path, path ^ 1)
// 实际遇到的东西
best = twoSelectOne(cur.nexts[best] != nil, best, best ^ 1)
// (path ^ best) 当前位位异或完的结果
ans |= (path ^ best) << move
cur = cur.nexts[best]
}
return ans
}
// O(N)
func maxXorSubarray2(arr []int) int {
if len(arr) == 0 {
return 0
}
max := math.MinInt64
// 0~i整体异或和
xor := 0
numTrie := NewNumTrie()
numTrie.add(0)
for i := 0; i < len(arr); i++ {
xor ^= arr[i] // 0 ~ i
max = getMax(max, numTrie.maxXor(xor))
numTrie.add(xor)
}
return max
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
