推荐方法

我建议使用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