The weekly challenge 303 - Task 2: Delete and Earn

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-303/#TASK2
 3 #
 4 # Task 2: Delete and Earn
 5 # =======================
 6 #
 7 # You are given an array of integers, @ints.
 8 #
 9 # Write a script to return the maximum number of points you can earn by
10 # applying the following operation some number of times.
11 #
12 ## Pick any ints[i] and delete it to earn ints[i] points.
13 ## Afterwards, you must delete every element equal to ints[i] - 1
14 ## and every element equal to ints[i] + 1.
15 #
16 ## Example 1
17 ##
18 ## Input: @ints = (3, 4, 2)
19 ## Output: 6
20 ##
21 ## Delete 4 to earn 4 points, consequently, 3 is also deleted.
22 ## Finally delete 2 to earn 2 points.
23 #
24 ## Example 2
25 ##
26 ## Input: @ints = (2, 2, 3, 3, 3, 4)
27 ## Output: 9
28 ##
29 ## Delete a 3 to earn 3 points. All 2's and 4's are also deleted too.
30 ## Delete a 3 again to earn 3 points.
31 ## Delete a 3 once more to earn 3 points.
32 #
33 ############################################################
34 ##
35 ## discussion
36 ##
37 ############################################################
38 #
39 # We create a recursive function. This function will calculate the maximum
40 # as follows:
41 # - return 0 on an empty list as input
42 # - for each element in the list, calculate how many points you would earn
43 #   by removing this element and all elements that are one bigger or smaller,
44 #   then calling the function recursively with the remaining elements
45 # - then take the maximum of all those earnings
46 #
47 
48 use strict;
49 use warnings;
50 
51 delete_and_earn(3, 4, 2);
52 delete_and_earn(2, 2, 3, 3, 3, 4);
53 
54 sub delete_and_earn {
55    my @ints = @_;
56    print "Input: (" . join(", ", @ints) . ")\n";
57    print "Output: " . delete_and_earn_recursive(@ints) . "\n";
58 }
59 
60 sub delete_and_earn_recursive {
61    my @ints = @_;
62    my $max = 0;
63    return 0 unless @ints;
64    foreach my $i (0..$#ints) {
65       my $val = $ints[$i];
66       my @tmp = ();
67       foreach my $elem ( @ints[0..$i-1,$i+1..$#ints]) {
68          next if $elem == $val - 1;
69          next if $elem == $val + 1;
70          push @tmp, $elem;
71       }
72       $val += delete_and_earn_recursive(@tmp);
73       $max = $val if $val > $max;
74    }
75    return $max;
76 }