39 lines
942 B
Text
39 lines
942 B
Text
Module LIS_example {
|
|
Function LIS {
|
|
LD=Stack.Size-1
|
|
dim L(0 to LD)
|
|
For i=0 to LD : Read V: L(i):=(V,):next
|
|
M=1
|
|
M1=LD
|
|
for i=LD-1 to 0
|
|
for j=LD to i+1
|
|
if Array(L(i))<Array(L(j)) then
|
|
' you can use either is the same
|
|
' if len(L(i))<=len(L(j)) then L(i)=Cons((Array(L(i)),), L(j))
|
|
if len(L(i))<=len(L(j)) then L(i)=(Array(L(i)),): Append L(i), L(j)
|
|
end if
|
|
next
|
|
if len(L(i))>=M then M1=i:M=Len(L(i))
|
|
next
|
|
=L(M1)
|
|
}
|
|
Const seq$="sequence", subseq$="Longest increasing subsequence"
|
|
Document doc$
|
|
Disp(seq$, (3,2,6,4,5,1))
|
|
Disp(subseq$, LIS(3,2,6,4,5,1))
|
|
Disp(seq$, (0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15))
|
|
Disp(subseq$, LIS(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15))
|
|
Print #-2,Doc$
|
|
Clipboard Doc$
|
|
|
|
Sub Disp(title$, m)
|
|
local n=each(m), s$
|
|
while n
|
|
s$+=", "+str$(Array(n),"")
|
|
end while
|
|
s$=trim$(mid$(s$, 2))
|
|
Doc$=title$+": "+s$+{
|
|
}
|
|
End Sub
|
|
}
|
|
LIS_example
|