Task — Arithmetic subsequences

You are given an array of integers, @ints. Write a script to find the length of the longest arithmetic subsequence in the given array. A subsequence is an array that can be derived from another array by deleting zero or more elements without changing the order of the remaining elements.

A subsquence is arithmetic if ints[i + 1] - ints[i] are all the same value for 0 <= i < ints.length - 1.

Analysis

Let's look at the first two integers - say they are 3 and 7. They differ by 4, and any arithmetic subsequence (AS) starting with that pair must continue with 7 + 4 = 11, 11 + 4 = 15 and so on. (I have slighly narrowed Mohammad's definition by asserting that an AS must have at least 3 members.) So I can scan along @ints looking for 11, and then for 15 and so on.

So I need only to check every possible pair of starting values a and b, differing by d (= b - a), and see if b + d, b + 2d and so on exist further on in @ints. This works even if d or any of @ints is zero or negative.

Interestingly, by using this method I don't need to use recursion or engage in the potentially expensive action of deleting values from @ints, so this is very fast even with several hundred values in @ints.

Try it 

Script

#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-06-12
use utf8;     # Week 221 task 2 - Arithmetic subsequence
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

my ($j, @ints);

arithmetic_subsequence(9, 4, 7, 2, 10, 12, 13);
arithmetic_subsequence(2, 7, -1, 9, -4, 11, -7, 33, -10);
arithmetic_subsequence(3, 3, 3);
arithmetic_subsequence(1, 2, 4, 7, 11, 16);
arithmetic_subsequence(2, 4, 6, 8, 21, 22, 23, 24);
arithmetic_subsequence(1, 2, 7, 19, 44, 123);
arithmetic_subsequence(1, 2);
arithmetic_subsequence(1, 2, 'x');

# larger example
for $j (0 .. 99) {
    push (@ints, int(rand(50)));
}
arithmetic_subsequence(@ints);

sub arithmetic_subsequence {
    
    my (@ints, $best, $last, $first, $second, $next, $length, $target, $explain, $best_explain, $delta);
    
    # initialise
    @ints = @_;
    return unless validate(@ints);
    $best = 0;
    $last = scalar @ints - 1;
    
    # loop over all possible first and second members of a subsequence
    for $first (0 .. $last - 2) {
        for $second ($first + 1 .. $last - 1) {
            
            # see how many subsequent members exist
            $delta = $ints[$second] - $ints[$first];
            $length = 2;
            $target = $ints[$second] + $delta;
            $explain = qq[($ints[$first], $ints[$second], ];
            
            # loop over rest of @ints to find them
            for $next ($second + 1 .. $last) {
                if ($ints[$next] == $target) {
                    $length ++;
                    $target += $delta;
                    $explain .= qq[$ints[$next], ];
                }
            }
            
            # new or new equal longest length found
            $explain = substr($explain, 0, -2) . '), ';
            if ($length > $best) {
                $best = $length;
                $best_explain = $explain;
            } elsif ($length == $best) {
                $best_explain .= $explain unless $best_explain =~ m|\Q$explain|;
            }
        }
    }
    
    # give verdict
    say qq[\nInput:  (] . join(', ', @ints) . ')';
    say qq[Output: ] . ($best > 2 ? qq[$best: ] . substr($best_explain, 0, -2) : q[No arithmetic subsequences]);
}

sub validate {
    
    my (@ints, $j, $error);
                
    # check input is valid
    @ints = @_;
    
    # must have >= 3 in @ints
    $error = qq[need at least 3 integers] if scalar @ints < 3;
    
    # must be integers
    for $j (@ints) {
        $error = qq[$j is not an integer] unless $j =~ m|^-?\d+$|;
    }
    return 1 unless $error;
    say qq[\nInput:  (] . join(', ', @ints) . qq[)\nOutput: Invalid input - $error];
    return 0;
}

Output

Input:  (9, 4, 7, 2, 10, 12, 13)
Output: 4: (4, 7, 10, 13)

Input:  (2, 7, -1, 9, -4, 11, -7, 33, -10)
Output: 5: (2, -1, -4, -7, -10)

Input:  (3, 3, 3)
Output: 3: (3, 3, 3)

Input:  (1, 2, 4, 7, 11, 16)
Output: 3: (1, 4, 7)

Input:  (2, 4, 6, 8, 21, 22, 23, 24)
Output: 4: (2, 4, 6, 8), (21, 22, 23, 24)

Input:  (1, 2, 7, 19, 44, 123)
Output: No arithmetic subsequences

Input:  (1, 2)
Output: Invalid input - need at least 3 integers

Input:  (1, 2, x)
Output: Invalid input - x is not an integer

Input:  (26, 9, 14, 10, 42, 44, 42, 24, 6, 14, 48, 19, 33, 4, 6, 4, 48, 31, 46, 1, 10, 37, 23, 28, 20, 36, 43, 22, 26, 43, 36, 7, 40, 19, 37, 8, 49, 4, 49, 39, 42, 10, 24, 22, 26, 31, 19, 41, 20, 33, 47, 17, 33, 32, 36, 46, 19, 44, 47, 27, 20, 25, 41, 14, 49, 28, 30, 15, 10, 2, 31, 47, 28, 45, 46, 36, 39, 0, 37, 9, 6, 33, 10, 38, 22, 8, 23, 25, 49, 34, 34, 3, 24, 46, 28, 43, 9, 27, 48, 24)
Output: 6: (6, 14, 22, 30, 38, 46), (19, 22, 25, 28, 31, 34), (33, 36, 39, 42, 45, 48), (1, 10, 19, 28, 37, 46), (23, 28, 33, 38, 43, 48), (20, 22, 24, 26, 28, 30)