2021-05-13：数组中所有数都异或起来的结果，叫做异或和。给定一个数组arr，返回arr的最大子数组异或和。

2021-05-13：数组中所有数都异或起来的结果，叫做异或和。给定一个数组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
    }
}

执行结果如下：

左神java代码复制版
左神java代码原版