CODEWITHSUNDEEP
algorithmmath
David Rogers
David Rogers

Reputation: 13

Maximizing difference of sums

Given a list of N distinct positive integers, partition the list into two sublists of n/2 size such that the difference between sums of the sublists is maximized. Assume that n is even and determine the time complexity.

I know, I know, it's a homework question. But the issue is not necessarily in solving it, but in understanding what exactly is being asked. I can safely say that half of the problem is simple to solve, but I don't think I get what is meant by

such that the difference between sums of the sublists is maximized.

Any help in illustrating the "plan of attack" on this would be appreciated

Upvotes: 1

Views: 2337

Answers (1)

Rahmat Waisi
Rahmat Waisi

Reputation: 1330

asuume you have this list

  • list : 1 ,1 , 2, 3, 1, 5, 6, 1, 2, 20

it means you can split it to sub lists with size of n/2 in many ways such like this

  • sub list 1 : 3, 1, 5, 6, 1
  • sub list 2 : 1 ,1 , 2, 2, 20

now calculate sum of each sub list

  • sum of sub list 1 is 16
  • sum of sub list 2 is 26
  • diffrence between them is : 10

but question want two sub lists such has this condition

  • question condition : difference between sums of the sublists is maximized.

it means between all ways that we can split main list into two sublists choose one way that has the question condition.

for example if we split above list into this lists

  • sub list 1 : 1 ,1 ,1 ,1 , 2

  • sub list 2 : 2, 3, 5 , 6 , 20

  • sum of sub list 1 is 6

  • sum of sub list 2 is 36
  • diffrence between them is : 30

which is more than last result and also is maximum

Upvotes: 1

Related Questions