如何劃分一個集合，使兩組之和的差值爲最大值

Question

設S是一組n個正整數，其中n是偶數。給出一種有效的算法來將S劃分成n/2個元素的兩個子集S1和S2，其中每個元素具有以下性質：S1中的元素 的總和與S2中的元素總和之間的差異是最大的。什麼時候你的算法的複雜性爲 。 這是算法的問題，但我無法弄清楚「S1中元素之和與S2中元素之和之間的差值最大」的含義。

Answer 1

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

Abs（Sum（最低值） - Sum（最高值））將是最大差異。