maximum difference in the summation of two subset-CodePudding

I have an array with N elements. I have to divide the array into two subset such that one subset has exactly M elements and the other subset has the rest. Dividing the items into subset in a way such that the difference in the summation of elements between the two subset is the maximum.

Example:

array size, N = 6

Number of element in one group, M = 3

elements = {2, 6, 3, 5, 10, 4}

The summation of subset 1 = 2 3 4 = 9

The summation of subset 2 = 6 5 10 = 21

The difference in subset = 21 - 9 = 12.

Note, this is the maximum difference possible.

I wrote following logic in python.

items = list(map(int, input().split()))
items.sort()
left = items[:M]
right = items[M:]
print(sum(right)-sum(left))

Not working when my input array is {100, 100, 150} and M = 2; Its giving me answer 50. But correct answer will be 150.

Constraints

1<= N <=1000 // N is size of array

1<= M < N // M is the size of subset

1<= array element <=10000000 // elements

What will be the approach to solve this problem?

CodePudding user response：

You need to sort first which you got it. Now you can take M elements from either from start or from the end. Consider both cases and take max.

items.sort()
left_sum = sum(items[:M])
left_sum_2 = sum(items[:-M])
right_sum = sum(items)-left
right_sum_2 = sum(items)-left_sum_2
print(max(abs(right_sum_2-left_sum_2), abs(right_sum-left_sum)))

CodePudding user response：

I suppose you should check two cases: the difference between the M lowest elements and the N-M highest ones, as you already did; and instead the difference between the M highest and the N-M lowest. Just return the biggest of the two. This is still O(n log n) by the way