CODEWITHSUNDEEP
algorithm
qrt
qrt

Reputation: 402

How to partition a set so that the difference between the sum of two sets is their maximum

Let S be a set of n positive integers, where n is even. Give an efficient algorithm to partition S into two subsets S1 and S2 of n/2 elements each with the property that the difference between the sum of the elements in S1 and the sum of the elements in S2 is maximum. What is the time complexity of your algorithm. This is a question from Algorithms, but I cannot figure out what's the meaning of "the difference between the sum of the elements in S1 and the sum of the elements in S2 is maximum".

Upvotes: 1

Views: 595

Answers (1)

Louis Ricci
Louis Ricci

Reputation: 21086

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

Abs(Sum(lowest values) - Sum(highest values)) will be the maximum difference.

Upvotes: 2

Related Questions