https://leetcode.com/problems/array-partition-i/#/description

image.png image.png

翻译

• 将长度为2n的数组分为n组,每组2个元素称为一个pair
• 将所有pair中较小的那个元素取出来,并求和
• 如何使得求和结果最大?即如何划分pair

思路

• min[列表最小元素, 任意元素] = 列表最小元素(注意不受任意元素的影响)
• 那么sum(min[ ], min[]...)与任意元素无关
• 为了使得sum最大, 每个pair中的任意元素也要小一些,这样使得较大的元素不会被"淹没掉"进而能对sum做出较大的贡献
• 对数组进行排序, min[array[i], array[i+1]] = array[i]
• 所以只要对排序后的数组每隔以为取元素求和即可

class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sum(sorted(nums)[::2])