This is the 27th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021.

Title description:

561. Array Splitting I – LeetCode (leetcode-cn.com)

Given an array of integers of length 2N, nums, your task is to divide the numbers into N pairs, such as (A1, b1), (a2, B2),… , (an, bn), maximizing the sum of min(ai, bi) from 1 to n.

Returns the maximum sum.

The sample a

Input: nums = [1,4,3,2] output: 4 explanation: all possible partitions (ignoring element order) are:  1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4, so the maximum sum is 4Copy the code

Example 2

Input: nums =,2,6,5,1,2 [6] output: 9: an optimal method for (2, 1), (2, 5), (6, 6), min (2, 1) + + min min (2, 5) (6, 6) = 1 + 2 + 6 = 9Copy the code

Tip:

  • 1 <= n <= 10^4
  • nums.length == 2 * n
  • -10^4 <= nums[i] <= 10^4

Thought analysis

greedy

Suppose the result of sorting is A1 <=b1<=a2<=b2<=… <=an<=bn

So who should A1 team up with?

A1, as the global minimum, will be added to the answer regardless of which group A1 is in, whereas A1’s partner will be permanently excluded.

In this case, it would be better to exclude a smaller number, namely, find a1’s “smallest partner” B1.

After A1 and B1 are processed, a2 is analyzed in the same way.

So, a1, A2… An will get the best result.

That’s the greedy way to think about it, and then there’s another interpretation of this solution in the official answer, which is to go along with the reasoning process, if you’re interested.

AC code

class Solution {
    fun arrayPairSum(nums: IntArray): Int {
        nums.sort()
        val len = nums.size
        var maxNum = 0
        for (index in 0 until len step 2){
             maxNum += nums[index]
        }   
        return maxNum
    }
}
Copy the code

conclusion

The same set of code, different ideas, greedy algorithms and mathematical proof, all lead to the same destination.

reference

Array Split I – Array split I – LeetCode (leetcode-cn.com)

Proof of The Correctness of Greedy Algorithm by Inverse Proof – Array splitting I-Force button (LeetCode) (leetcode-cn.com)