首页 > 试题广场 >

子数组的最大异或和

[编程题]子数组的最大异或和
  • 热度指数:1414 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
数组异或和的定义:把数组中所有的数异或起来得到的值。给定一个整型数组arr,其中可能有正、有负,有零,求其中子数组的最大异或和。

输入描述:
输出包含两行,第一行一个整数n,代表数组arr长度,第二个n个整数,代表数组arr


输出描述:
输出一个整数,代表其中子数组的最大异或和。
示例1

输入

4
3 -28 -29 2

输出

7

说明

{-28,-29}这个子数组的异或和为7,是所有子数组中最大的 

备注:
时间复杂度,额外空间复杂度
头像 王清楚
发表于 2020-10-15 17:37:55
记 表示数组前 个数的异或和,就是区间的异或和那如果想知道以 位置结尾的子数组的最大异或和,只需要知道 和 中的数异或的最大值就可以了。(即这些区间异或和的最大值)那怎么样快速地知道 和 中的数异或和的最大值呢?我们利用前缀树的结构,对每一个,从最高位到最低位判断。这里需要注意一下,因为我们想 展开全文