Task — Max diff

You are given an array of integers having four or more elements. Write a script to find two pairs of numbers from this list (four numbers total) so that the absolute difference between their products is as large as possible.

Examples

Example 1
Input: @ints = (5, 9, 3, 4, 6)
Output: 42
Pair 1: (9, 6)
Pair 2: (3, 4)
Product Diff: (9 * 6) - (3 * 4) => 54 - 12 => 42

Example 2
Input: @ints = (1, -2, 3, -4)
Output: 10
Pair 1: (1, -2)
Pair 2: (3, -4)

Example 3
Input: @ints = (-3, -1, -2, -4)
Output: 10
Pair 1: (-1, -2)
Pair 2: (-3, -4)

Example 4
Input: @ints = (10, 2, 0, 5, 1)
Output: 50
Pair 1: (10, 5)
Pair 2: (0, 1)

Example 5
Input: @ints = (7, 8, 9, 10, 10)
Output: 44
Pair 1: (10, 10)
Pair 2: (7, 8)

Analysis

This is a frustrating challenge in that in some cases there is a simple answer. For example, first sort the provided list, and:

• if all the numbers are >= 0 then the pairs are the first two and last two from the sorted list, and
• the same is true if they are all <= 0.

But if neither condition is true, it gets more complicated.

So I initially went with a foolproof but increasingly expensive solution which is to generate all the variations of 4 numbers from the supplied array and testing them each to see which gives the largest difference.

I have included in my worked examples 50 random numbers in the range -250 .. +250 and my solution takes only about 10 seconds on my quite slow processor, so unless this were needed in a time-critical application I think it would be adequate.

Addendum ...

Having given this more thought after submitting my answer (henceforth Method 1) I have deduced that the 4 numbers which form the two pairs satisfying the challenge will always be a subset of the first and last 3 numbers of the supplied set, or the whole set if it has fewer than 6 members.

It is still quite a complicated matter to deduce the desired answer, but regardless of the size of the supplied set, checking all the combinations of 4 items from 6 is very fast, completing in milliseconds. So that is my Method 2, which is used by the 'try it' below.

Try it 

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2025-09-15
use utf8;     # Week 339 - task 1 - Max diff
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;
use Algorithm::Combinatorics 'variations';

max_diff(5, 9, 3, 4, 6);
max_diff(1, -2, 3, -4);
max_diff(-3, -1, -2, -4);
max_diff(10, 2, 0, 5, 1);
max_diff(7, 8, 9, 10, 10);
max_diff(0, 0, 0, 0, 0);
max_diff(5, 5, 5, 5, 5);
max_diff(-5, -5, -5, -5, -5);
max_diff(-20, 40, -60, 80);
max_diff(-20, 40, -60, 80, -100);
max_diff(20, -40, 60, -80, 100, -120);

# 20 random numbers in [-1000 .. +1000]
my @ints;
push @ints, int(rand(501)) - 250 for 1 .. 50;
max_diff(@ints);

sub max_diff {
    
    my ($best, $iter, $c, $diff, $pairs, @nums, @ints);
    
    say qq[\nInput:  (] . join(', ', @_) . ')';
    @ints = sort {$a <=> $b} @_;
    
    if (@ints <= 20) {
        
        # METHOD 1
        
        # initialise
        $best = -1;
        $iter = variations(\@ints, 4);
        
        # iterate over all variations
        while ($c = $iter->next) {
            
            # is this one the best so far?
            $diff = abs($c->[0] * $c->[1] - $c->[2] * $c->[3]);
            if ($diff > $best) {
                $best = $diff;
                $pairs = qq[($c->[0], $c->[1]), ($c->[2], $c->[3])];
            }
        }
        say qq[Output1: $best: $pairs];
    }
    
    # METHOD 2
    
    # take first and last 2 plus 3rd and 3rd last
    # if they are not already there
    @nums = ($ints[0], $ints[1], $ints[-2], $ints[-1]);
    push @nums, $ints[2] if @ints > 4;
    push @nums, $ints[-3] if @ints > 5;
    @nums = sort {$a <=> $b} @nums;
    $best = -1;
    $iter = variations(\@nums, 4);
  
    # iterate over all variations
    while ($c = $iter->next) {
        
        # is this one the best so far?
        $diff = abs($c->[0] * $c->[1] - $c->[2] * $c->[3]);
        if ($diff > $best) {
            $best = $diff;
            $pairs = qq[($c->[0], $c->[1]), ($c->[2], $c->[3])];
        }
    }
    say qq[Output2: $best: $pairs];
}

Output

Input:  (5, 9, 3, 4, 6)
Output1: 42: (3, 4), (6, 9)
Output2: 42: (3, 4), (6, 9)

Input:  (1, -2, 3, -4)
Output1: 10: (-4, 3), (-2, 1)
Output2: 10: (-4, 3), (-2, 1)

Input:  (-3, -1, -2, -4)
Output1: 10: (-4, -3), (-2, -1)
Output2: 10: (-4, -3), (-2, -1)

Input:  (10, 2, 0, 5, 1)
Output1: 50: (0, 1), (5, 10)
Output2: 50: (0, 1), (5, 10)

Input:  (7, 8, 9, 10, 10)
Output1: 44: (7, 8), (10, 10)
Output2: 44: (7, 8), (10, 10)

Input:  (0, 0, 0, 0, 0)
Output1: 0: (0, 0), (0, 0)
Output2: 0: (0, 0), (0, 0)

Input:  (5, 5, 5, 5, 5)
Output1: 0: (5, 5), (5, 5)
Output2: 0: (5, 5), (5, 5)

Input:  (-5, -5, -5, -5, -5)
Output1: 0: (-5, -5), (-5, -5)
Output2: 0: (-5, -5), (-5, -5)

Input:  (-20, 40, -60, 80)
Output1: 4000: (-60, 80), (-20, 40)
Output2: 4000: (-60, 80), (-20, 40)

Input:  (-20, 40, -60, 80, -100)
Output1: 9200: (-100, 80), (-60, -20)
Output2: 9200: (-100, 80), (-60, -20)

Input:  (20, -40, 60, -80, 100, -120)
Output1: 15200: (-120, 100), (-80, -40)
Output2: 15200: (-120, 100), (-80, -40)

Input:  (142, -222, 49, -89, -128, 40, -204, 199, -220, 
-193, 26, 136, -41, 218, -122, 245, 182, 180, 80, 145, 
78, -137, 45, 122, 62, 10, 196, 231, -100, 48, 126, -234, 
-152, -100, -1, 36, -37, 22, 171, 244, 113, -122, -196, 
250, 149, 200, 102, -139, -67, -244)
Output2: 120786: (-244, 244), (245, 250)