Please explain: The question doesn't make sense.


  • 64
    D

    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


  • 15

    I don't understand the question either.


  • 70
    I

    @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


  • 0

    @Ivorzz thanks


  • 4
    H

    @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.


  • 16
    Z

    @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?


  • 10
    I

    @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! :)


  • 0
    H

    @Ivorzz
    Very clear, thank you for your help.


  • 0
    H

    @zxyelc
    Thank you for your explanation.


  • 0
    C

    Thanks for the explain, I'm reeeeeally confused by the description


  • 0
    J

    Thank you for the explaination.


  • 0
    G

    Actually,Why do we want to sort the array?because we want to minimize the loss,in the other words,we want the smallest number of collocation with the number is relatively small,in this way, when we ignore this relatively small number, the loss will be reduced。


  • 0
    J

    @Ivorzz Thanks pal, it helped me too.


  • 0
    C

    I learned a lot from the explanation here. Thanks to everybody. Leetcode really needs to rephrase the question.


  • 1

    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.


  • 0
    W

    @Ivorzz thanks


  • 1
    W

    @zxyelc very good


  • 0

    @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


  • 0
    J

    if we think in your idea and according to the problem description,the min of(1,4)is 1,and the min of(2,3)is 2,so the sum would be 1+2=3.


  • 0
    K

    @djordan we have to take the minimum


Log in to reply
 

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