Question

Formatted question description: https://leetcode.ca/all/561.html

 561. Array Partition I

 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:
 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].

Algorithm

Since we want to maximize the sum of the smaller values ​​in each pair, then the two numbers in each pair must be as close as possible, because if the difference is too large and we only take the smaller number, then the big number will be wasted Lost.

Understand this, we only need to sort the array, and then every two in the order is a pair, we take out the first number in each pair and add up the smaller value.

Code

Java

    class Solution {
        public int arrayPairSum(int[] nums) {
            //sort the array
            Arrays.sort(nums);
            int sum = 0;
            for(int i = 0; i < nums.length; i += 2) {
                sum += nums[i];
            }
            return sum;
        }
    }

All Problems

All Solutions