子数组最大异或和

数组异或和的定义：把数组中所有数异或起来失去的值。

给定一个整型数组：arr，其中可能有正、有负、有零，求其子数组的最大异或和

【举例】

arr = 【3】

数组中只有 1 个数，所以只有一个子数组，就是这个数组自身，最大异或和为 3

arr = 【3，-28，-29，2】

子数组有很多，然而【-28，-29】这个子数组的异或和为 7，是所有子数组中最大的。

剖析：

异或和没有枯燥性。两个小的数的异或和可能比两个大数的异或和大。

解法一：暴力算法

对每一个以 i 为开始和以 j 为结尾的子数组，进行异或和计算，获取全局最大的异或和，就是答案。

工夫复杂度：$O(N^3)$

工夫复杂度：O(1)

import sysdef max_xor(arr):    if not arr: return 0    res = -sys.maxsize    for i in range(len(arr)):        for j in range(i, len(arr)):             # 窗口:arr[i,j+1],计算窗口内数据的异或和            xor = 0            for k in range(i, j + 1):                xor ^= arr[k]            res = max(res, xor)    return res

解法二：前缀异或和

前缀和的性质：

  1. 归零率：A ^ A = 0
  2. 恒等率：A ^ 0 = A

根据上述两个性质能够推导出：

$C = A \oplus B \Longrightarrow \\ C \oplus A = A \oplus B \oplus A \Longrightarrow \\ C \oplus A = B \oplus 0 \Longrightarrow \\ A \oplus C = B$

依据前缀异或和能够计算出任意子数组的异或和。

工夫复杂度：$O(N^2)$

工夫复杂度：O(N)

def max_xor1(arr):    if not arr: return 0      # 前缀异或和    prefix_sum = [arr[0]]    for i in range(1, len(arr)):        prefix_sum.append(arr[i] ^ prefix_sum[-1])    res = -sys.maxsize    for i in range(len(arr)):        s = 0 if i == 0 else prefix_sum[i - 1]        for j in range(i, len(arr)):            # 窗口:arr[i,j+1]            xor = prefix_sum[j] ^ s            res = max(res, xor)    return res

解法三：前缀树 + 贪婪

由解法二可知：$C = A \oplus B \Longrightarrow B = C \oplus A$

即：$arr[2...5] = arr[0...5] \oplus arr[0...2]$

  • arr[0..5] 与 0 联合示意：arr[0...5] 子数组的异或和
  • arr[0..5] 与 arr[0] 联合示意：arr[1...5] 子数组的异或和
  • arr[0..5] 与 arr[0...1] 联合示意：arr[2...5] 子数组的异或和
  • arr[0..5] 与 arr[0...2] 联合示意：arr[3...5] 子数组的异或和
  • ...

与谁联合异或和大，应答的子数组就是要找的子数组。

目前不晓得 arr[0...5] 抉择哪个？在解法二中是枚举尝试，咱们当初想通过前缀树构建一种规定（贪婪策略）来减速寻找最佳联合子数组。

<font color=red>贪婪策略：在 arr[0..j] 抉择 arr[ 0..i ] 联合过程中，优先投合高位变成 1（高位为1，对应值更大）。</font>

如下图：arr[0...j] 的异或和的二进制模式【0,1,1,0】，从高位A逐个匹配。因为 0 ^ 1 = 1，所以抉择 1 的分支（ A --> C ）， 在 F 地位，尽管最期待走的门路是 0 ，然而没有 0 门路所以只能走 1 门路。整条门路【1,0,1,1】 就是 arr[0...j] （【0,1,1,0】）最佳联合的子数组对应的异或和。【0,1,1,0】^ 【1,0,1,1】= 【1,0,1,1】此时【1,0,1,1】 就是的返回后果 arr[0..j]。

前缀树

# 将所有的前缀异或和，退出到 NumTrie，并依照前缀树组织class NumTrie:    def __init__(self):        self.root = Node()    def add(self, num):        cur = self.root        # move 向右位移多少位        for move in range(31, -1, -1):            # 获取对应位上的数字（0 或者 1）            path = (num >> move) & 1            cur.nexts[path] = cur.nexts[path] if cur.nexts[path] else Node()            cur = cur.nexts[path]    # num 最心愿遇到的门路，后果返回：最大的异或和    # 工夫复杂度：O(32)    def max_xor(self, num):        cur = self.root        # 返回值(num ^ 最优抉择)        res = 0        for move in range(31, -1, -1):            # 获取对应位上的数字（0 或者 1）            path = (num >> move) & 1            # sum 该位的状态，最期待的门路（如果sum 位是0，期待path =1，否则 path = 0）            # 留神：如果是符号位是 1（正数），期待 path = 1，异或后是 0（负数）            #      如果是符号位是 0（负数），期待 path = 0，异或后是 0（负数）            best = path if move == 31 else path ^ 1            # 最期待走的门路  --> 理论门路            best = best if cur.nexts[best] else best ^ 1            # 留神：本代码是 python，左移 31 位不会变为正数，python 会将 int 转为 long 变为更大的数            # 如果是 java：res |= (path ^ best) << move            tmp = 1            if move == 31 and num < 0:                tmp = -1            res |= tmp * (path ^ best) << move            cur = cur.nexts[best]        return res

工夫复杂度：$O(N)$

工夫复杂度：O(N)

def max_xor2(arr):    if not arr: return 0    res = -sys.maxsize    trie = NumTrie()    trie.add(0)    # 一个数没有时，异或和为 0    xor = 0    for i in range(len(arr)):        # xor 等于 0 ~ i 异或和        xor ^= arr[i]        # trie 装着所有：一个数也没有（0），0~1，0~2，0~3...0~i-1 的异或和        res = max(res, trie.max_xor(xor))        trie.add(xor)    return res

对数器

import randomdef check():    max_value = 10    for i in range(100):        arr = [int(random.random() * max_value) - int(random.random() * max_value) for _ in               range(int(random.random() * max_value))]        res = max_xor(arr)        res1 = max_xor1(arr)        res2 = max_xor2(arr)        if res != res1 or res != res2:            print(i, "ERROR", arr, "res=", res, "res1=", res1, "res2=", res2)    print("NICE")

本文由mdnice多平台公布