解决k分区变化的算法

Question

对于我的算法设计课程的家庭作业来了这个脑筋急转弯:

Given a list of N distinct positive integers, partition the list into two 
sublists of n/2 size such that the difference between sums of the sublists 
is maximized.
Assume that n is even and determine the time complexity.

乍一看,解决方案似乎是

1. 通过mergesort对列表进行排序
2. 选择n/2位置
3. 对于大于的所有元素,添加到高数组
4. 对于低于所有元素,添加到低数组

这将具有时间复杂性 O((n log n)+ n)

这个问题有更好的算法选择吗？

Answer 1

由于您可以在O(n)时间内计算中位数,因此您也可以在O(n)时间内解决此问题.计算中值,并将其用作阈值,创建高阵列和低阵列.

有关在O(n)时间内计算中位数的信息,请参见http://en.wikipedia.org/wiki/Median_search.