Re: Puzzle: Longest Increasing Sequence

[demerphq]

Heres my go. Originally I had something that was performing between 2N-1 and N*((N+1)/2), but kaif provided the insight I needed to get it to N log N when he pointed out that you only need to store one path of a given length at any one time.

BTW, I wanted a single routine that could return either the indexes or the actual values, so this is a little clunkier than it need be if you didnt care about the indexes.

Update: I was wrong, the worse case run time for this routine is (N+1)/2*N, which is O(N²).

use strict;
use warnings;

sub long_inc_seq {
    my ( $ar, $as_idx )= @_;

    return $ar
        unless $ar and @$ar>1;

    my @seq= ( [] );
    my $opcount= 0;

    foreach my $cur ( 0 .. $#$ar ) {
        my $item= $ar->[$cur];
        for( my $idx= $#seq; $idx >= 0; $idx-- ) {
            $opcount++;
            if ( !$idx || $ar->[ $seq[$idx][-1] ] < $item ) {
                if ( ! $seq[$idx+1] || $ar->[ $seq[$idx+1][-1] ]  > $i
+tem ) {
                    @{$seq[$idx+1]}= ( @{$seq[$idx]}, $cur );
                } else {
                    last;
                }
            }
        }
    }
    my $best= pop @seq;
    $best= [ @$ar[@$best] ]
        if !$as_idx;
    return wantarray ? ( $best, $opcount ) : $best;
}

sub lg($) { log($_[0])/log(2) }


sub print_it {
    my ( $ar, $best, $opcount )= @_;
    my @out=map { " " x length $ar->[$_]  } 0 .. $#$ar;
    $out[$_]= $ar->[$_] for @$best;
    print "[", join( " ", @$ar ), "]\n";
    print "(", join( " ", @out ), ")\n";
    printf "Steps: %d, Expected: %d\n",
        $opcount, @$ar * lg(@$ar);
    print "\n";
}

sub main {
    my @t= ( 1 .. 10 );
    my @ar= (
        [ 8, 6, 5, 1, 9, 3, 7, 4, 2, 10 ],
        [ 3, 10, 6, 1, 5, 7, 8, 2, 4, 9],
        [ 7, 8, 9, 10, 1, 2, 3, 4, 5, 6],
        \@t,
        [ reverse @t ],
    );

    foreach my $ar ( @ar ) {
        print_it( $ar, long_inc_seq( $ar, 1 ) );

    }
}

main();