给定一个数组，你必须找到最大可能的两个相等的和，你可以排除元素。
即 1,2,3,4,6 是给定的数组
我们最多可以有两个相等的和为 6+2 = 4+3+1
即 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、A-B(两组的和与差)。
然后对于数组中的每个元素，尝试将其添加到 A 或 B，或两者都不添加。
跟踪和/差的优势在于，您只需跟踪每个差异的单个值，即您看到的此差异的总和的最大值。
为了提高效率，我建议您按从小到大的顺序遍历元素，并在达到目前看到的最大差异后停止更新 DP。
也可以只存储差值的绝对值，忽略大于25000的差值(因为差值不可能从这一点回到0)。
Python 示例代码
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
关于algorithm - 给定一个数组，你必须找到最大可能的两个相等的和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52244676/