33 lines
2.1 KiB
Rexx
33 lines
2.1 KiB
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*/
|