#! perl -slw
use strict;
use Time::HiRes qw[ time ];
use Data::Dump qw[ pp ]; $Data::Dump::WIDTH = 500;

our $S //= 0; srand $S if $S;
our $N //= 20;

sub LIS {
    my $X = shift;
    my( @P, @M );

    my $L = 0;
    for my $i ( 0 .. $#$X ) {
        ## Binary search for the largest positive j = L such that X[M[j]] < X[i]
        my $lo = 1;
        my $hi = $L;
        while( $lo <= $hi ) {
            my $mid = int( ( $lo + $hi ) / 2 );
            if( $X->[ $M[ $mid ] ] < $X->[ $i ] ) {
                $lo = $mid + 1;
            }
            else{
                $hi = $mid - 1;
            }
        }
        ## After searching, lo is 1 greater than the length of the longest prefix of X[i]
        my $newL = $lo;

        ## The predecessor of X[i] is the last index of the subsequence of length newL-1
        $P[ $i ] = $M[ $newL - 1 ];
        $M[ $newL ] = $i;

        if( $newL > $L ) {
            ## If we found a subsequence longer than any we've found yet, update L
            $L = $newL;
        }
    }
    ## Reconstruct the longest increasing subsequence
    my @S;
    my $k = $M[ $L ];
    for my $i ( reverse 0 .. $L-1 ) {
        $S[ $i ] = $X->[ $k ];
        $k = $P[ $k ];
    }
    return @S;
}


my @data = map int( rand $N ), 1 .. $N;

my $start = time;
my @best = LIS( \@data );
printf "best(%d): @best\n", scalar @best;
printf "Took %.3f seconds\n", time() - $start;