Longest increasing subsequence: Difference between revisions
Content added Content deleted
m (corrected a misspelling, added a section header to the first topic to properly place the table-of-contents (TOC) --- (this happens more often than one would think).) |
(→{{header|REXX}}: added the REXX computer programming language for this task.) |
||
Line 2,008: | Line 2,008: | ||
<pre>'(2 4 5) |
<pre>'(2 4 5) |
||
'(0 2 6 9 11 15)</pre> |
'(0 2 6 9 11 15)</pre> |
||
=={{header|REXX}}== |
|||
{{trans|VBScript}} |
|||
<lang rexx>/*REXX program finds & displays the longest increasing subsequence from a list of #'s.*/ |
|||
$.=; $.1= 3 2 6 4 5 1 /*define the 1st list to be examined. */ |
|||
$.2= 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 /* " " 2nd " " " " */ |
|||
do j=1 while $.j\==''; say /* [↓] process all of the list for LIS*/ |
|||
say ' input: ' $.j /*display the (original) input list. */ |
|||
call LIS $.j /*invoke the LIS function. */ |
|||
say 'output: ' result /*display the output (result from LIS)*/ |
|||
end /*j*/ |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
LIS: procedure; parse arg x; n= words(x); if n==0 then return '' |
|||
p.=; m.= p. |
|||
do #=1 to n; _= # - 1; @._= word(x, #) /*build an array (@) from input.*/ |
|||
end /*#*/ |
|||
L= 0 |
|||
do j=0 to n-1; lo= 1 |
|||
HI= L |
|||
do while LO<=HI; middle= (LO+HI) % 2 |
|||
_= m.middle /*create a temporary value for @ index.*/ |
|||
if @._<@.j then LO= middle + 1 |
|||
else HI= middle - 1 |
|||
end /*while*/ |
|||
newLO= LO |
|||
_= newLO - 1 /*create a temporary value for M index.*/ |
|||
p.j= m._ |
|||
m.newLO= j |
|||
if newLO>L then L= newLO |
|||
end /*i*/ |
|||
k= m.L; $= /* [↓] build a list for the result. */ |
|||
do L; $= @.k $; k= p.k /*perform this DO loop L times. */ |
|||
end /*i*/ |
|||
return strip($) /*the result has an extra leading blank*/</lang> |
|||
{{out|output|text= when using the internal default input:}} |
|||
<pre> |
|||
input: 3 2 6 4 5 1 |
|||
output: 2 4 5 |
|||
input: 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 |
|||
output: 0 2 6 9 11 15 |
|||
</pre> |
|||
=={{header|Ring}}== |
=={{header|Ring}}== |