Array Partition I. I am not clear of the question


  • 0
    R

    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?


  • 3

    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.