Given a list of integers, I have to maximize the sum of product of cardinality of the each subsets into the sum of the corresponding subset.
For eg - $A : -1,-2-3,2,1,3,100$.
Then maximum sum can be obtained by using the whole list as 1 set instead of breaking into subsets i.e $(100(sum)*7(cardinality))$
I could think of considering every combination of subsets. I was also thinking to take all positives into single set and each negative as an individual set but this won't give optimal answer.
Is there an efficient way to find subsets ?
Clearly all the positive elements should go in one subset to get the multiplier as high as possible. All the negative elements that are not in that subset should go in singletons to make the multiplier as small as possible. The only question is which negative elements should be in the set with the positives. Start with all the elements in one set and compare with taking the most negative number out to its own set. If that improves the result, try taking out the next most negative number. Keep going until the result doesn't improve and you have the optimum.