| 17 October 2025 | Challenge 339 |
Different Peaks
Task 1: Max Diff
Submitted by: Mohammad Sajid Anwar
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 difference between their products is as large as possible.
In the end return the max difference.
With Two pairs (a, b) and (c, d), the product difference is (a * b) - (c * d).
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)
Solution
First insight on this task: The solution for a specific list depends not only on the structure of the given data - especially the number of positive and negative elements - but also on the values themselves.
Secondly: For the maximum product difference \(ab - cd\) there are two cases:
- \(ab\) is the maximum product over all pairs and \(cd\) the minimum product over the remaining pairs or
- \(cd\) is the minimum product over all pairs and \(ab\) is the maximum product over the remaining pairs.
Here are two examples to illustrate these insights:
- The numbers are \(i = (4, 3, 2, 1, -6, -7)\).
The global maximum product is \((-6)\cdot(-7) = 42\), the minimum product from the remaining list is \(2 \cdot 1 = 2\) with a difference of \(42 - 2 = 40\).
The global minimum product is \(4 \cdot (-7) = -28\), the maximum product from the remaining list is \(3 \cdot 2 = 6\) with a difference of \(6 - (-28) = 34\)
The maximum difference of \(40\) is taken with the maximum product. - The numbers are \(i = (5, 3, 2, 1, -6, -7)\).
The global maximum product is \((-6)\cdot(-7) = 42\), the minimum product from the remaining list is \(2 \cdot 1 = 2\) with a difference of \(42 - 2 = 40\).
The global minimum product is \(5 \cdot (-7) = -35\), the maximum product from the remaining list is \(3 \cdot 2 = 6\) with a difference of \(6 - (-35) = 41\)
The maximum difference of \(41\) is taken with the minimum product.
The maximum product can be found as:
- the product of the list’s elements if it has only two elements or
- the maximum of:
- the product of the two largest elements if there are at least two positive elements and
- the product of the two smallest elements if there are at least two negative elements
The minimum product can be found as:
- the product of the list’s elements if it has only two elements or
- the product of the largest and the smallest element if there are at least one positive and one negative element or
- the product of the two largest elements if there are only negative elements or
- the product of the two smallest elements if there are only positive elements
After identifying a global minimum or maximum product, the corresponding elements have to be invalidated for the following operation on the remaining list.
Though this approach may look a bit complicated, it has a complexity of \(\mathcal{O}(n)\), which may be regarded as optimal.
Putting everything together results in a somewhat lengthy solution:
use strict;
use warnings;
use experimental 'signatures';
use PDL;
use PDL::NiceSlice;
sub max_diff (@n) {
my $n = long @n;
$n->badflag(1);
my $pd = null;
for my $subs ([\&find_max, \&find_min, 1], [\&find_min, \&find_max, -1]) {
my $nc = $n->copy;
my $m1 = &{$subs->[0]}($nc);
my $m2 = &{$subs->[1]}($nc->where($nc->isgood));
$pd = $pd->append($subs->[2] * ($m1 - $m2));
}
max $pd;
}
sub remove_prod ($l) {
my $prod = $l->prod;
$l .= $l->badvalue;
$prod;
}
sub find_max ($n) {
goto &remove_prod if $n->nelem == 2;
my ($pos, $neg) = which_both $n >= 0;
my $max_ind = null;
if ($pos->nelem >= 2) {
$max_ind = $max_ind->glue(1, maximum_n_ind($n, 2));
}
if ($neg->nelem >= 2) {
$max_ind = $max_ind->glue(1, minimum_n_ind($n, 2));
}
my $max = $n->index1d($max_ind)->prodover->maximum_ind;
return remove_prod($n($max_ind(,($max))));
}
sub find_min ($n) {
goto &remove_prod if $n->nelem == 2;
my ($pos, $neg) = which_both $n >= 0;
if (!$neg->isempty && !$pos->isempty) {
return remove_prod($n(cat(($n->minmaximum)[2, 3])));
} elsif ($pos->isempty) {
return remove_prod($n(maximum_n_ind($n, 2)));
} else {
return remove_prod($n(minimum_n_ind($n, 2)));
}
}
See the full solution to task 1.
Task 2: Peak Point
Submitted by: Mohammad Sajid Anwar
You are given an array of altitude gain.
Write a script to find the peak point gained.
Example 1
Input: @gain = (-5, 1, 5, -9, 2)
Output: 1
start: 0
1st change: 0 + (-5) = -5
2nd change: -5 + 1 = -4
3rd change: -4 + 5 = 1
4th change: 1 + (-9) = -8
5th change: -8 + 2 = -6
max(0, -5, -4, 1, -8, -6) = 1
Example 2
Input: @gain = (10, 10, 10, -25)
Output: 30
start: 0
1st change: 0 + 10 = 10
2nd change: 10 + 10 = 20
3rd change: 20 + 10 = 30
4th change: 30 + (-25) = 5
max(0, 10, 20, 30, 5) = 30
Example 3
Input: @gain = (3, -4, 2, 5, -6, 1)
Output: 6
start: 0
1st change: 0 + 3 = 3
2nd change: 3 + (-4) = -1
3rd change: -1 + 2 = 1
4th change: 1 + 5 = 6
5th change: 6 + (-6) = 0
6th change: 0 + 1 = 1
max(0, 3, -1, 1, 6, 0, 1) = 6
Example 4
Input: @gain = (-1, -2, -3, -4)
Output: 0
start: 0
1st change: 0 + (-1) = -1
2nd change: -1 + (-2) = -3
3rd change: -3 + (-3) = -6
4th change: -6 + (-4) = -10
max(0, -1, -3, -6, -10) = 0
Example 5
Input: @gain = (-10, 15, 5)
Output: 10
start: 0
1st change: 0 + (-10) = -10
2nd change: -10 + 15 = 5
3rd change: 5 + 5 = 10
max(0, -10, 5, 10) = 10
Solution
Taking the maximum of the cumulated sum over the numbers prepended by a zero.
use strict;
use warnings;
use PDL;
sub peak_point {
max cumusumover pdl 0, @_;
}
See the full solution to task 2.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.