给定一个数组，您必须找到最大可能的两个相等和，可以排除元素。
ie 1,2,3 ，4,6 给定数组，我们可以得到两个等于6 + 2 = 4 + 3 + 1的和
即4,10,18，22，我们可以得到两个相等的总和，即18 + 4 = 22
您可以用什么方法分开解决这个问题从蛮力中查找所有计算并检查两个可能的相等总和？
edit 1：数组元素的最大个数不超过N == 50，每个元素最多1< = K< = 1000
编辑2：这是我的解决方法 ideone/cAbe4g ，在每种情况下，给定的时间限制为5秒，这会花费太多时间。
编辑3： -总元素总和不能大于1000。
解决方案推荐方法 <我建议使用DP解决此问题，而不是跟踪A，B（两者的大小集），您可以跟踪A + B，AB（两个集的总和和差）。
然后针对数组中的每个元素，尝试将其添加到A中，或者B，或者都不是。
跟踪总和/差的好处是，您只需要跟踪每个差的单个值，即 p
为了获得更高的效率，我建议您按从小到大的顺序依次遍历元素，以提高效率。一旦达到迄今为止所看到的最大差异，就停止更新DP。
您还可以仅存储差异的绝对值，而忽略大于25000的任何差异（因为差将无法从此点恢复为0）。
Python示例代码 从集合中导入defaultdict def max_equal_sum（E）： D = defaultdict（int）＃从Abs差异映射到lar gest sum D [0] = 0＃以E的和为0和的差开始：＃遍历数组中的每个元素D2 = D.copy（）＃如果元素在D.items（）中被d，s跳过，则可以保持当前的总和和差异：＃d是差，s是总和 s2 = s + a＃s2是新的总和对于[da，d + a]中的d2：＃d2是新差异 D2 [abs（d2）] = max（D2 [abs（d2）]，s2）＃以最大和进行更新D = D2 return D [0] / 2＃答案是A + B之和的一半，差为0 print max_equal_sum（[1,2,3,4,6 ]）＃打印8 print max_equal_sum（[4,10,18,22]）＃打印22
Given an array, you have to find the max possible two equal sum, you can exclude elements.
i.e 1,2,3,4,6 is given array we can have max two equal sum as 6+2 = 4+3+1
i.e 4,10,18, 22, we can get two equal sum as 18+4 = 22
what would be your approach to solve this problem apart from brute force to find all computation and checking two possible equal sum?
edit 1: max no of array elements are N <= 50 and each element can be up to 1<= K <=1000
edit 2: Here is my solution ideone/cAbe4g, it takes too much time where given time limit is 5 seconds say for each case.
edit 3:- Total elements sum cannot be greater than 1000.
解决方案Recommended approach
I suggest solving this using DP where instead of tracking A,B (the size of the two sets), you instead track A+B,A-B (the sum and difference of the two sets).
Then for each element in the array, try adding it to A, or B, or neither.
The advantage of tracking the sum/difference is that you only need to keep track of a single value for each difference, namely the largest value of the sum you have seen for this difference.
For added efficiency, I recommend you iterate through the elements in order from smallest to largest and stop updating the DP once the largest difference seen so far is reached.
You can also only store the absolute value of the difference, and ignore any difference greater than 25000 (as it will be impossible for the difference to return to 0 from this point).
Python example code 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