How to resolve the algorithm Longest increasing subsequence step by step in the Raku programming language

Published on 12 May 2024 09:40 PM
#Raku

How to resolve the algorithm Longest increasing subsequence step by step in the Raku programming language

Table of Contents

Problem Statement

Calculate and show here a longest increasing subsequence of the list: And of the list: Note that a list may have more than one subsequence that is of the maximum length.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Longest increasing subsequence step by step in the Raku programming language

Source code in the raku programming language

sub lis(@d) {
    my @l = [].item xx @d;
    @l[0].push: @d[0];
    for 1 ..^ @d -> $i {
        for ^$i -> $j {
            if @d[$j] < @d[$i] && @l[$i] < @l[$j] + 1 {
                @l[$i] = [ @l[$j][] ]
            }
        }
        @l[$i].push: @d[$i];
    }
    return max :by(*.elems), @l;
}

say lis([3,2,6,4,5,1]);
say lis([0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]);


sub lis(@deck is copy) {
    my @S = [@deck.shift() => Nil].item;
    for @deck -> $card {
        with first { @S[$_][*-1].key > $card }, ^@S -> $i {
            @S[$i].push: $card => @S[$i-1][*-1] // Nil
        } else {
            @S.push: [ $card => @S[*-1][*-1] // Nil ].item
        }
    }
    reverse map *.key, (
        @S[*-1][*-1], *.value ...^ !*.defined
    )
}

say lis <3 2 6 4 5 1>;
say lis <0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15>;

You may also check:How to resolve the algorithm Flatten a list step by step in the Scheme programming language
You may also check:How to resolve the algorithm Averages/Mode step by step in the PHP programming language
You may also check:How to resolve the algorithm Erdős-Nicolas numbers step by step in the Wren programming language
You may also check:How to resolve the algorithm Determinant and permanent step by step in the Fortran programming language
You may also check:How to resolve the algorithm Sub-unit squares step by step in the ALGOL 68 programming language