Longest increasing subsequence: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 83: | Line 83: | ||
<pre>[ 2 4 5 ] |
<pre>[ 2 4 5 ] |
||
[ 0 2 6 9 11 15 ]</pre> |
[ 0 2 6 9 11 15 ]</pre> |
||
=={{header|Icon}} and {{header|Unicon}}== |
|||
The following works in both languages: |
|||
<lang unicon>procedure main(A) |
|||
every writes((!lis(A)||" ") | "\n") |
|||
end |
|||
procedure lis(A) |
|||
pt := [[A[1]]] | fail |
|||
r := pt[1] |
|||
every v := !A do { |
|||
every p := !pt do { |
|||
if put(p, p[-1] < v) then { |
|||
if *p > *r then r := p |
|||
} |
|||
else p[-1] := (p[-2] < v) |
|||
} |
|||
put(pt,[v]) |
|||
} |
|||
return r |
|||
end</lang> |
|||
Sample runs: |
|||
<pre> |
|||
->lis 3 2 6 4 5 1 |
|||
3 4 5 |
|||
->lis 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 |
|||
0 4 6 9 11 15 |
|||
-> |
|||
</pre> |
|||
=={{header|Java}}== |
=={{header|Java}}== |