Task — Array pairings

We are given an array of integers having an even number of elements.

We are asked to consider all possible pairs of values from the array and to find the two pairs for which the sum of the smaller elements is a maximum.

Analysis

Let's start by reverse sorting the array, so that $array[0] is the largest element.

Suppose the sorted array is a, b, c, d ... z. The pair with the largest minimum is (a, b), because a is the largest number in the array, and for b to be the minimum number in a pair it has to be less than a, but it also is the largest element in the array other than a.

In the same way, now that a and b are accounted for, (c, d) is the pair with the second largest minimum - d. The largest possible sum of the minima is thus b + d.

So in summary, if you reverse sort the array, the answer to the task is the sum of the 2nd and 4th members of the sorted array.

And, ok, sorting is expensive, but, firstly I imagine that the Perl 'sort' is done in compiled code which is faster than interpreted Perl, and secondly, finding all the pairs in an unsorted array will take two nested loops which is quite a bit of work, so I doubt the difference is significant.

Try it 

Script

#!/usr/bin/perl

# Peter Campbell Smith - 2023-02-27

use v5.28;
use utf8;
use warnings;

# Task: You are given an array of integers having even number of elements. Divide the array into
# all possible pairs of elements. Write a script to find the two pairs whose minima sum to the
# maximum value.

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/206/1


max_min(1, 2, 3, 4);
max_min(0, 2, 1, 3);
max_min(3, 7, 4, 12, 5, 1, 0, 10, 9, 2, 11, 13, -1, 6, 2);

sub max_min {
    
    # reverse sort the array numerically
    my @array = reverse sort { $a <=> $b} @_;
    
    # show the results (see blog for explanation)
    say qq[\nInput:  \@array = (] . join(', ', @_) . qq[)];
    say qq[Output: ] . ($array[1] + $array[3]) . 
        qq[ = min($array[0], $array[1]) + min($array[2], $array[3])];
}

Output

Input:  @array = (1, 2, 3, 4)
Output: 4 = min(4, 3) + min(2, 1)

Input:  @array = (0, 2, 1, 3)
Output: 2 = min(3, 2) + min(1, 0)

Input:  @array = (3, 7, 4, 12, 5, 1, 0, 10, 9, 2, 11, 13, -1, 6, 2)
Output: 22 = min(13, 12) + min(11, 10)