Question: Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
the example given was,
[1,4,3,2] and the answer 4
is it that i need to check all the possible 8 arrays that are of length n , and compute their sums and look for the greatest sum of them all?
i am not clear of the question. Will someone please explain it to me?
You are given 2n integers, say m1,m2,m3....m2n. Now you need to find a way to group them into two parts with equal number. e.g. a1,a2,a3...an, and b1,b2,b3...bn. Now, find a way to match numbers from two parts together, then have (a1,b1), (a2,b2)...(an,bn). Sum all the min(ai,bi), so you have sum = min(a1,b1) + min(a2,b2) ... + min(an,bn).
Your job is to find the maximum possible sum. A brute force way is just try all the possible pairs of numbers and find the maximum one. However, there is a very simple way. Hope this will help.