Longest increasing subsequence: Difference between revisions
m
→Dynamic programming: 'strict' compliant
Thundergnat (talk | contribs) m (→{{header|Ring}}: Remove vanity tags) |
SqrtNegInf (talk | contribs) m (→Dynamic programming: 'strict' compliant) |
||
Line 1,447:
===Dynamic programming===
{{trans|Perl 6}}
<lang Perl>
sub lis {
my @l = map [], 1 .. @_;
push @{$l[0]}, +$_[0];
Line 1,458 ⟶ 1,460:
push @{$l[$i]}, $_[$i];
}
my ($max, $l) = (0, []);
for (@l) {
($max, $l) = (scalar(@$_), $_) if @$_ > $max;
Line 1,466 ⟶ 1,468:
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;</lang>
{{out}}
<pre>2 4 5
| |||