2.18　数组分割

有一个没有排序、元素个数为2n的正整数数组，要求：如何能把这个数组分割为元素个数为n的两个数组，并使两个子数组的和最接近？

分析与解法

从题目中可以分析出，题目的本质就是要从2n个整数中找出n个，使得它们的和尽可能地靠近所有整数之和的一半。

【解法一】

看到这个题目后，一个直观的想法是：

先将数组的所有元素排序为a₁＜a₂＜…＜a_2N，

将它们划分为两个子数组S₁＝[a₁，a₃，a₅，…，a_2N－1]和S₂＝[a₂，a₄，a₆，…，a_2N]，

从S₁和S₂中找出一对数进行交换，使得SUM（S₁）和SUM（S₂）之间的值尽可能的小，直到找不到可对换的。这种想法的缺陷是得到的S₁和S₂并不是最优的。

【解法二】

假设2n个整数之和为SUM。从2n个整数中找出n个元素的和，不管如何接近SUM/2，同样都会存在大于SUM/2或者小于SUM/2的情况。在求解这个问题时，大于或小于SUM/2没有本质的区别。因此，可以只考虑小于等于SUM/2的情况。

比较直观地来说，可以用动态规划来解决这个问题。具体分析如下：

可以把任务分成2N步，第k步的定义是前k个元素中任意i个元素的和，所有可能的取值之集合为S_k（只考虑取值小于等于SUM/2的情况）。

然后将第k步拆分成两个小步。即首先得到前k－1个元素中，任意i个元素，总共能有多少种取值，设这个取值集合为S_k－1＝{v_i}。第二步就是令S_k＝S_k－1∪{v_i＋arr[k]}，即可完成第k步。

伪代码实现如下：

代码清单2-36

从有效性来分析，整个代码是一个三重循环，目的就是执行insert。这个代码实际执行insert的次数至多是4^N次（枚举所有元素在与不在的情况），因此可以认为复杂度是O（4^N）。

既然算法的时间复杂度是N的指数级，因此在N很大时，效率很低。我们不得不考虑设计一种时间复杂度是N的多项式函数的方法。考虑的出发点是，是否有另一种拆分第k步的方法。

【解法三】

解法二的拆分方法需要遍历S_k－1＝{v_i}的元素，由于S_k－1＝{v_i}的元素个数随着k的增大而增大，所以导致了解法二的效率低下。能不能设计一个算法使得第k步所花费的时间与k无关呢？

我们不妨倒过来想，原来是给定S_k－1＝{v_i}，求S_k。那我们能不能给定S_k的可能值v和arr[k]，去寻找v－arr[k]是否在S_k－1＝{v_i}中呢？由于S_k可能值的集合的大小与k无关，所以这样设计的动态规划算法其第k步的时间复杂度与k无关。

代码如下：

代码清单2-37

利用如上的算法，时间复杂度将为O（N²* Sum）。

讨论

虽然解法三对于N是多项式时间算法，但当SUM很大而N很小时，比如对于arr＝{10⁹，10⁸，10⁸＋1，10⁹＋1}，这个解法是很不合适的，所以我们应该根据具体的问题选用合适的方法。

扩展问题

如果数组中有负数，怎么办？