数组中所有数都异或起来的结果，叫做异或和。给定一个数组arr，可以任意切分成若干个不相交的子数组。其中一定存在一种最优方案，使得切出异或和为0的子数组最多。返回这个最多数量。
准备一个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
}
}执行结果如下：
