给定一个数组，您必须找到最大可能的两个相等和，可以排除元素。
即1,2,3,4,6给定数组，我们最多可以有两个等于6 + 2 = 4 + 3 + 1的和
1,2,3,4,6
即4,10,18，22，我们可以得到两个相等的总和，即18 + 4 = 22
除了蛮力查找所有计算并检查两个可能的相等和之外，您将采用什么方法解决此问题？
编辑1：数组元素的最大数量为N <= 50，每个元素最大为1 <= K <= 1000
编辑2：这是我的解决方案https://ideone.com/cAbe4g，这花费了太多时间，对于每种情况，给定的时间限制是5秒。
编辑3：-总元素总数不能大于1000。
我建议使用DP解决此问题，而不是跟踪A，B（两组的大小），而是跟踪A + B，AB（两组的总和和差）。
然后，对于数组中的每个元素，尝试将其添加到A或B中，或都不添加到两者中。
跟踪和/差的好处是，你只需要跟踪单个值的每个差异，即 最大的 ，你已经看到了这种差异的总和值。
为了提高效率，我建议您按从小到大的顺序对元素进行迭代，并在达到目前为止看到的最大差异后停止更新DP。
您也只能存储差的绝对值，而忽略大于25000的任何差（因为从这一点开始差将不可能恢复为0）。
from collections import defaultdict def max_equal_sum(E): D=defaultdict(int) # Map from abs difference to largest sum D[0]=0 # Start with a sum and difference of 0 for a in E: # Iterate over each element in the array D2=D.copy() # Can keep current sum and diff if element is skipped for d,s in D.items(): # d is difference, s is sum s2 = s+a # s2 is new sum for d2 in [d-a,d+a]: # d2 is new difference D2[abs(d2)] = max(D2[abs(d2)],s2) # Update with largest sum D=D2 return D[0]/2 # Answer is half the sum of A+B for a difference of 0 print max_equal_sum([1,2,3,4,6]) # Prints 8 print max_equal_sum([4,10,18,22]) # Prints 22
