Longest increasing subsequence: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|Ring}}: Remove vanity tags) |
SqrtNegInf (talk | contribs) m (→Dynamic programming: 'strict' compliant) |
||
Line 1,447: | Line 1,447: | ||
===Dynamic programming=== |
===Dynamic programming=== |
||
{{trans|Perl 6}} |
{{trans|Perl 6}} |
||
<lang Perl> |
<lang Perl>use strict; |
||
sub lis { |
|||
my @l = map [], 1 .. @_; |
my @l = map [], 1 .. @_; |
||
push @{$l[0]}, +$_[0]; |
push @{$l[0]}, +$_[0]; |
||
Line 1,458: | Line 1,460: | ||
push @{$l[$i]}, $_[$i]; |
push @{$l[$i]}, $_[$i]; |
||
} |
} |
||
my ($max, $l) = 0, []; |
my ($max, $l) = (0, []); |
||
for (@l) { |
for (@l) { |
||
($max, $l) = (scalar(@$_), $_) if @$_ > $max; |
($max, $l) = (scalar(@$_), $_) if @$_ > $max; |
||
Line 1,466: | Line 1,468: | ||
print join ' ', lis 3, 2, 6, 4, 5, 1; |
print join ' ', lis 3, 2, 6, 4, 5, 1; |
||
print join ' ', lis 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15; |
print join ' ', lis 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15;</lang> |
||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>2 4 5 |
<pre>2 4 5 |