给定一个整数数组，需要将其拆分为四个
框中的框的XOR的总和是最大的。
I/P--[1,2,1,2,1,2]
输出/输出——9
说明：框1--[1,2]
框2--[1,2]
方框3--[1,2]
方框4--[]
我尝试过使用递归，但对于更大的测试用例失败
时间复杂度是指数的。我期待用动态
编程。
def max_Xor(b1,b2,b3,b4,A,index,size):
if index == size:
return b1+b2+b3+b4
m=max(max_Xor(b1^A[index],b2,b3,b4,A,index+1,size),
max_Xor(b1,b2^A[index],b3,b4,A,index+1,size),
max_Xor(b1,b2,b3^A[index],b4,A,index+1,size),
max_Xor(b1,b2,b3,b4^A[index],A,index+1,size))
return m
def main():
print(max_Xor(0,0,0,0,A,0,len(A)))
提前谢谢！!
最佳答案
有几件事可以加速你的算法：
构建一些启动逻辑：在框1和框2被区分之前，在框3中放入任何内容都没有意义实际上，您通常应该有一个优先顺序，以防止以不同的顺序重复配置。
记住你的逻辑；这样可以避免重复计算。
对于大的情况，利用什么值代数存在。
最后一项可能是最大的节省例如，如果你的最长的数字包括几个5位和4位的数字，那么考虑更短的数字是没有意义的，直到你把这些数字放在框中，获得领先的位的最大优势。如果只有四个框，则不能有一个3位数字的num支配一个错位的5位数字。
您的目标是将5位数字的奇数放入3个或全部4个框中；与此相反，请仅检查此“悲观”是否使剩余数字的第4位变为“悲观”例如，给定6个5位数字（范围16-31）和少数几个小数字（0-7），您首先要考虑的是只处理将5位数字划分为（3、1、1、1）的组合，因为这样会使每个集合中的有价值的5位打开。
对于输入中的值更为偶数的混合，您还需要考虑如何为类似的“keep it odd”启发式分配4位注意，当你从大到小地工作时，你只需要担心保持它的奇数性，并注意以下几点。
这些技术应该可以让你修剪你的递归足够及时完成。