Python, explained with greedy algorithm

  • 0

    The thinking is to pick up the largest available number every time, and then the sum will be maximized.

    Starting from the 1st largest number, we cannot pick it up because it required to be paired with a larger number.
    The 2nd largest number we can pick it up, by pairing it with the 1st largest number.
    The 3rd largest number we cannot pick it up because all larger number have been used. One may think pairing up the 3rd and the 2nd largest number, but that'd make the sum smaller than pairing the 2nd largest number with the 1st largest number.

    Since we are checking the numbers in descending order, we want to add the encountered number to the sum as soon as possible.

    def arrayPairSum(self, nums):
            numsCopy = sorted(nums, reverse=True)
            ret = 0
            for i in range(1, len(numsCopy), 2):
                ret += numsCopy[i]
            return ret

Log in to reply

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