给定一个数组,你必须找到最大可能两个相等的总和

Question

给定一个数组,你必须找到最大可能两个相等的和,你可以排除元素.

即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.

Answer 1

推荐的方法

我建议使用DP来解决这个问题,而不是跟踪A,B(两组的大小),而是跟踪A + B,AB(两组的总和和差异).

然后,对于数组中的每个元素,尝试将其添加到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