Algorithm of the Day Minimization of the sum of the greatest number pairs, proof of the correctness of greedy solutions | Python topic month

This article is participating in Python Theme Month. See the link for details

Topic describes

This is the minimum sum of the largest pair in the array on LeetCode 1877. The difficulty is medium.

Tag: “Greedy.”

The sum of a number pair (a,b) is equal to a plus b. The maximum pair sum is the largest pair sum in an array of pairs.

For example, if we have pairs (1,5), (2,3) and (4,4), the maximum sum of pairs is Max (1+5, 2+3, 4+4) = Max (6, 5, 8) = 8. Given an array nums of even length n, divide the elements in nums into n / 2 pairs such that:

• Each element in numS is in exactly one pair, and
• The maximum pair sum has the smallest value.

In the optimal pair partition scheme, you return the minimum maximum pair sum.

Example 1:

Input: nums = [3,5,2,3] output: 7 explanation: the elements in the array can be divided into pairs (3,3) and (5,2). The maximum sum of pairs is Max (3+3, 5+2) = Max (6, 7) = 7.Copy the code

Example 2:

Input: nums = [3,5,4,2,4,6] output: 8 explanation: elements in the array can be divided into pairs of numbers (3,5), (4,4), and (6,2). The maximum sum of pairs is Max (3+5, 4+4, 6+2) = Max (8, 8, 8) = 8.Copy the code

Tip:

• n == nums.length
• 2 <= n <=
  $10^5$
• N is even.
• 1 <= nums[i] <=
  $10^5$

Basic analysis & proof

Intuitively, we would think that pairing “smaller” and “larger” numbers would be a good way to avoid “larger number pairs.”

So let’s prove that this is true.

Assuming that numsnumsnums itself is orderly, since we want to split Numsnumsnums into n/2n /2n /2 pairs, according to the conjecture, the sequence of the number pairs we get is:

In other words, the pairs that make up the answer must be smaller numbers taken from the left of the ordered sequence, larger numbers taken from the right of the ordered sequence, and symmetric with the center of the array.

Assumes that the maximum number of is (nums [I], nums [j]) (nums [I], nums [j]) (nums [I], nums [j]), in which I < < ji ji < j, Ans =nums[I]+ NUMs [j]ans=nums[I]+nums[j]ans =nums[I]+nums[j]

It is proved that there is no other number pair combination better than (nums[I], NUMs [j])(nums[I],nums[j])(nums[I],nums[j]) :

Assumes that the number of (nums [p], nums [q]) (nums [p], nums [q]) (nums [p], nums [q]) with (nums [I], nums [j]) (nums [I]. Nums [I],nums[j],nums[j])

Next, discuss in different cases:

• Adjusted for (nums [I], nums [p]) (nums [I], nums [p]) (nums [I], nums [p]) and (nums [q], nums [j]) (nums [q], nums [j]) (nums [q], nums [j]) : Nums [q]+nums[j] +nums[j]nums[q] +nums[j] Obviously nums [q] + nums [j] > = nums [I] + nums = ansnums [j] [q] + nums [j] > = nums nums [I] + [j] = ansnums [q] + nums [j] > = nums [I] + nums = ans [j]. We want to minimize the maximum sum of pairs, so this adjustment doesn’t make the answer better;

• Adjusted for (nums [I], nums [q]) (nums [I], nums [q]) (nums [I], nums [q]) and (nums [p], nums [j]) (nums [p], nums [j]) (nums [p], nums [j]) : The maximum number of answers for Max ⁡ (nums nums [I] + [q], nums nums [p] + [j]) = nums nums [p] + [j] > = nums [I] + nums = ans \ [j] Max (nums nums [I] + [q], nums[p] + nums[j]) = nums[p] + nums[j] >= nums[i] + nums[j] = Nums ansmax (nums [I] + [q], nums nums [p] + [j]) = nums nums [p] + [j] > = nums [I] + nums = ans [j]. We want to minimize the maximum sum of pairs, so this adjustment doesn’t make the answer better;

The above analysis generalizes to every “asymmetric” number pair pairing.

So far, we have proved that adjusting the original symmetric number pair to asymmetric number pair will not make the answer better, that is, greedy solution can obtain the optimal solution.

greedy

Select numsnumsnums, numsnums, numsnums, numsnums, numsnums, numsnums, numsnums, numsnums, numsnums, numsnums

Java code:

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = nums[0] + nums[n - 1];
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            ans = Math.max(ans, nums[i] + nums[j]);
        }
        returnans; }}Copy the code

Python 3 code:

class Solution:
    def minPairSum(self, nums: List[int]) - >int:
        nums.sort()
        n = len(nums)
        ans = nums[0] + nums[n - 1]
        for i in range(1, n//2):
            ans = max(ans, nums[i] + nums[n - 1 - i])
        return ans
Copy the code

• O(nlog⁡n)O(n\log{n})O(nlogn)
• Space complexity: O(log⁡n)O(\log{n})O(logn)

The last

This is the No.1877 article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.