Anonymous user
Longest increasing subsequence: Difference between revisions
→{{header|REXX}}: added the REXX computer programming language for this task.
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:
<pre>'(2 4 5)
'(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}}==
| |||