algorithm - 如何划分一个集合，使得两个集合之和的差是它们的最大值

Question

令 S 为一组 n 个正整数，其中 n 为偶数。给个高效将 S 划分为两个子集 S1 和 S2 的算法，每个子集包含 n/2 个元素具有元素之和之间的差异的属性S1 中的元素和 S2 中的元素之和最大。现在几点了你的算法的复杂性。Algorithms的一道题，我一直搞不懂“S1中元素之和与S2中元素之和之差最大”是什么意思。

Answer 1

S = RadixSort(S) // O(N)
S1 = S[0..(N/2)-1]
S2 = S[N/2..N-1]

Abs(Sum(lowest values) - Sum(highest values)) 将是最大差异。