问如何划分一个集合，使两个集合之和之间的差值达到最大值。
EN

Stack Overflow用户

提问于 2015-09-28 14:12:36

回答 1查看 466关注 0票数 1

设S是n个正整数集合，其中n是偶数。给出了一种将S划分为n/2元素的两个子集S1和S2的有效算法，每个子集的性质是: S1中的元素之和与S2中元素之和的差值最大。算法的时间复杂度是多少？这是算法中的一个问题，但我不知道“S1中元素之和与S2中元素之和之间的差异是最大的”的含义。

回答已采纳

发布于 2015-09-28 14:35:23

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

Abs(和(最低值)-和(最高值))将是最大的差异。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/32825205

复制

相似问题

问如何划分一个集合，使两个集合之和之间的差值达到最大值。EN