So if we are given [1.2.3.4], is this a possibility?
(1,4) and (2,3)
In that case, won't the correct answer be 5. Our goal is to get the largest possible sum from the above 4 integers. So, how can 4 be the answer?
Thanks
@djordan The goal is to get the largest possible sum of MIN of the pair.
So for the example [1, 2, 3, 4], the best pairs are (1, 2) and (3, 4).
min(1, 2) + min(3, 4) = 1 + 3 = 4
@Ivorzz said in Please explain: The question doesn't make sense.:
@djordan The goal is to get the largest possible sum of MIN of the pair.
So for the example [1, 2, 3, 4], the best pairs are (1, 2) and (3, 4).
min(1, 2) + min(3, 4) = 1 + 3 = 4
Could anyone explain why best pairs are (1, 2) and (3, 4)? Thanks a lot.
@howy
Because it is the largest possible sum of MIN of the pair.
Just try another one like (1, 4) and (2, 3)
step one: min(1, 4) = 1, min(2, 3) = 2;
step two: add the mins, sum = 1 + 2 = 3;
step three: compare this to our best pairs, 3 < 4.
Obviously, 4 is larger, so (1, 2) and (3, 4) are better pairs than (1, 4) and (2, 3).
The point here is: for each pair, we calculate min(a, b), but for sum of all the mins, we want the largest sum.
Is this clear for you?
@howy The intuitive way of reasoning is that, to get the the sum of mins as large as possible, we need to make the min numbers as large as possible. Essentially, we're sacrificing large numbers by grouping them with the small numbers. To make the small numbers as large as possible, the best way is to group them with their adjacent large numbers.
For example, (1, 3) and (2, 4) are not best pairs since you're sacrificing 3 by grouping it with 1. (1, 2) and (3, 4) is better since now 3 is the MIN and can contribute to the sum.
Mathematically, @shawngao has made a very nice proof in another thread.
Hope this helps! :)
Same here. The description of the question should definitely be improved. Especially about how it explains in the example, "the maximum sum of pairs is 4", which should be improved as "the maximum sum of the minimum of pairs is min(1, 2) + min(3, 4) = 1 + 3 = 4
".
Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4.
@djordan We get the smallest number in the N group and add them together, and we want their sum to be the largest of all possibilities, so we can take the largest number of 2N integers (and perhaps the same number) , It takes an integer and it forms a group, and we want the last sum to be the largest, so the best practice is to give it a second largest integer, and so on