Task — Maximum product

You are given a list of 3 or more integers. Write a script to find the 3 integers whose product is the maximum and return it.

Analysis

We are asked for 'the maximum' and I am going to assume that's the nearest to plus infinity. So given -3 and 2 then 2 is the maximum.

With that settled, here is the algorithm:

• Reverse sort the list by absolute value using
  sort { abs($b) <=> abs($a) }.
• Take the first three numbers in the list and multiply then together to give $product
• If $product is positive, or if the list has only 3 numbers - that's the answer.
• If $product is negative, subtract from $product the last negative item of the three, and multiply $product by the next positive item (or zero) in the list - and that's the answer.

Here's a couple of examples. The sorted list is 7, -6, 5, -4, 3, 2, 1

We multiply 7 x -6 x 5 = -210. That's negative, so we remove -6 which is the last negative number in our triplet. We can't use -4 because it's negative, but we can use 3, so now we have 7 x 5 x 3 = 105.

Now let's start with -7, -6, 5, -4, -3, 2, -1).

We multiply -7 x -6 x 5 = 210. That's positive, so that's the answer.

However, if all the numbers in the list are negative the above won't work, for example if the list is -7, -6, -5, -4, -3. Clearly no three numbers from that list will multiply to a positive number, so in this case the maximum product - see my assumption above - is the product of the last 3 numbers in the sorted list, in this case -5 x -4 x -3 = -60

You might ask 'what if one or more of the numbers are zero?' A few experiments show that the algorithm still works, for example: 3, 2, 0 yields zero, 4, 3, 2, 0 yields 24 and -3, -2, -1, 0 yields -3 x -2 x 0 = 0, which is correct as no other product of three of that list yields a positive result.

Try it 

#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-05-22
use utf8;     # Week 218 task 1 - Maximum product
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

max_product(1, 2, 3, 4, 5);
max_product(-8, 2, -9, 0, -4, 3);
max_product(-9, -8, -7, -6, -5);
max_product(5, 6, 0);

sub max_product {
    
    my (@list, $product, $count, $j, $last_negative, $explain, $k, $last, $negatives);
    
    @list = @_;
    say qq[\nInput:  (] . join(', ', @list) . ')';
    @list = sort { abs($b) <=> abs($a) } @list;
    
    $product = 1;
    $count = 3;
    $last = scalar @list - 1;
    die 'Not enough data' if $last < 2;
    
    # check for special case where list is all negatives
    $negatives = 0;
    $negatives += $_ < 0 ? 1 : 0 for @list;
    
    # not the special case
    if ($negatives != $last + 1) {
        for $k (0 .. $last) {

            # multiply next number into product
            $j = $list[$k];
            $product *= $j;
            $explain .= qq[$j x ];
            
            # note last negative one in case we need to back it out
            $last_negative = $j if $j < 0;
            $count --;
            
            # if we've multiplied 3 and the result is +ve then we're done
            if ($count == 0) {
                last if $product >= 0;
                
                # and we're done if there are no more entries
                last if $k == $last;
                
                # else we need to back out the last negative one and try again
                $product /= $last_negative;
                $explain =~ s|$last_negative x ||;
                $count = 1;
            }       
        }
        
    # special case
    } else {
        $product = $list[$last - 2] * $list[$last - 1] * $list[$last];
        $explain =  qq[$list[$last - 2] x $list[$last - 1] x $list[$last] x ];
        
    }
    say qq[Output: $product = ] . substr($explain, 0, -3);
}

Output

Input:  (1, 2, 3, 4, 5)
Output: 60 = 5 x 4 x 3

Input:  (-8, 2, -9, 0, -4, 3)
Output: 216 = -9 x -8 x 3

Input:  (-9, -8, -7, -6, -5)
Output: -210 = -7 x -6 x -5

Input:  (5, 6, 0)
Output: 0 = 6 x 5 x 0