Task — Delete and earn

You are given an array of integers, @ints. Write a script to return the maximum number of points you can earn by applying the following operation some number of times. Pick any $ints[$i] and delete it to earn $ints[$i] points. Afterwards, you must delete every element equal to $ints[$i] - 1 and every element equal to $ints[$i] + 1.

Examples

Example 1
Input: @ints = (3, 4, 2)
Output: 6
Delete 4 to earn 4 points, consequently, 3 is also 
deleted.
Finally delete 2 to earn 2 points.

Example 2
Input: @ints = (2, 2, 3, 3, 3, 4)
Output: 9
Delete a 3 to earn 3 points. All 2's and 4's are also 
deleted too.
Delete a 3 again to earn 3 points.
Delete a 3 once more to earn 3 points.

Analysis

This challenge can be solved using recursion.

The work is done by sub d_and_e which takes a current state with no, some or all @ints deleted, and checks each possibility of cashing another number (and deleting others according to the rules) and then calling itself recursively until no numbers are left.

When it reaches the point of all numbers being cashed or deleted, it checks to see whether this is the best earner, and if so records that.

Try it 

Try running the script with any input:

Your @ints =

example: 2, 2, 3, 3, 3, 4, 4

⤡

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2025-01-06
use utf8;     # Week 303 - task 2 - Delete and earn
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

my ($max_earnings, $max_explain);

delete_and_earn(2, 2, 3, 3, 3, 4);
delete_and_earn(2, 2, 3, 3, 4, 4);
delete_and_earn(1, 3, 5, 7, 9);
delete_and_earn(1, 2, 3, 4, 5);

sub delete_and_earn {
    
    my (@ints, @amounts, @new_amounts, $j);
    
    # initialise
    @ints = @_;
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . ')';
    
    # set up $amounts[$j] = no of $j's in @ints
    $amounts[$_] ++ for @ints;
    for $j (0 .. $#amounts) {
        $amounts[$j] = 0 unless defined $amounts[$j];
    }
    $max_earnings = 0;
    
    # call d_and_e
    d_and_e(\@amounts, 0, '');
    say qq[Output: $max_earnings (] . substr($max_explain, 3) . ')';
}

sub d_and_e {
    
    my (@amounts, @new_amounts, $more, $earnings, $new_earnings, $j, $explain, $new_explain);
    
    # descend one level
    @amounts = @{$_[0]};
    $earnings = $_[1];
    $explain = $_[2];
    
    # find each uncashed number
    for $j (0 .. $#amounts) {
        next unless $amounts[$j] > 0;
        
        # cash it
        $new_earnings = $earnings + $j;
        $new_explain = qq[$explain + $j];
        if ($new_earnings > $max_earnings) {
            $max_earnings = $new_earnings;
            $max_explain = $new_explain;
        }
        
        # update amounts for recursive call
        @new_amounts = @amounts;
        $new_amounts[$j] --;
        $new_amounts[$j - 1] = 0 if $j > 0;
        $new_amounts[$j + 1] = 0 if $j < $#amounts;
        d_and_e(\@new_amounts, $new_earnings, $new_explain);
    }
}

Output

Input:  @ints = (2, 2, 3, 3, 3, 4)
Output: 9 (3 + 3 + 3)

Input:  @ints = (2, 2, 3, 3, 4, 4)
Output: 12 (2 + 2 + 4 + 4)

Input:  @ints = (1, 3, 5, 7, 9)
Output: 25 (1 + 3 + 5 + 7 + 9)

Input:  @ints = (1, 2, 3, 4, 5)
Output: 9 (1 + 3 + 5)