2021-05-17：数组中所有数都异或起来的结果，叫做异或和。给定一

2021-05-17：数组中所有数都异或起来的结果，叫做异或和。给定一个数组arr，可以任意切分成若干个不相交的子数组。其中一定存在一种最优方案，使得切出异或和为0的子数组最多。返回这个最多数量。

福大大 答案2021-05-17：

准备一个map，key存前缀异或和，value存数组序号。

dp[i]是0到i的异或和为0的子数组最多的数量。

代码用golang编写。代码如下：

 package main

import "fmt"

func main() {
    arr := []int{3, 2, 1, 0, 0, 2, 1, 3, 3, 2, 3, 1, 0, 0, 0}
    ret := mostXor(arr)
    fmt.Println(ret)
}

// 时间复杂度O(N)的方法
func mostXor(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    N := len(arr)
    dp := make([]int, N)

    // key 某一个前缀异或和
    // value 这个前缀异或和上次出现的位置(最晚！)
    map0 := make(map[int]int)
    map0[0] = -1
    // 0~i整体的异或和
    xor := 0
    for i := 0; i < N; i++ {
        xor ^= arr[i]
        if _, ok := map0[xor]; ok { // 可能性2
            pre := map0[xor]
            if pre == -1 {
                dp[i] = 1
            } else {
                dp[i] = dp[pre] + 1
            }
        }
        if i > 0 {
            dp[i] = getMax(dp[i-1], dp[i])
        }
        map0[xor] = i
    }
    return dp[N-1]
}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}  

执行结果如下：

***

[左神java代码](