LeetCode 561. Array Partition I

Description:

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.

Note:

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

Example:

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

Solution:

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        int halfSize = nums.size() / 2;
        for(auto i = 0; i < halfSize; ++i){
            sum += nums[2 * i];
        }
        return sum;
    }
};

Assume there are $2n$ integers in the array, which are sorted ascendingly to form array

where \(s_i \leq s_j (i < j; \ i,j \in [1, 2n])\).

To find the greatest sum of $n$ elements, there is no doubt that the result is

However, we are only able to sum up \(\min(s_i, s_j)\ (i \neq j)\). That is to say, there is no way that \(s_{2n}\) can be added into our result, for it is greater than or equal to any other element in the array. That is, it is basically “useless” in the array. Consider the rest of the array, the greatest element is \(s_{2n-1}\). By grouping it up with \(s_{2n}\), we are able to add it into our final result. The rest of the greatest sum can be derived in the same manner.