LeetCode 561. Array Partition I [Easy]

Problem:

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.

 

Example 1:

Input: [1,4,3,2]

Output: 4

Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

 

Note:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

Summary:

Sort the nums first. Then we will have the maximum numbers in ascending order from each min pair.

Since we are only adding even position number (0 indexes as even position), we will add all those numbers and it will return the maximum sum of min pair.

 

Code:

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        max_sum = 0
        nums.sort()
        
        for i, n in enumerate(nums):
            if i % 2 == 0:
                max_sum += n
        
        return max_sum

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]