38 lines
919 B
Plaintext
38 lines
919 B
Plaintext
function lis(sequence X, integer N = length(X))
|
|
sequence P = repeat(0,N)
|
|
sequence M = repeat(0,N)
|
|
integer len = 0
|
|
for i=1 to N do
|
|
integer lo = 1
|
|
integer hi = len
|
|
while lo<=hi do
|
|
integer mid = ceil((lo+hi)/2)
|
|
if X[M[mid]]<X[i] then
|
|
lo = mid + 1
|
|
else
|
|
hi = mid - 1
|
|
end if
|
|
end while
|
|
if lo>1 then
|
|
P[i] = M[lo-1]
|
|
end if
|
|
M[lo] = i
|
|
if lo>len then len = lo end if
|
|
end for
|
|
sequence res = repeat(0,len)
|
|
if len>0 then
|
|
integer k = M[len]
|
|
for i=len to 1 by -1 do
|
|
res[i] = X[k]
|
|
k = P[k]
|
|
end for
|
|
end if
|
|
return res
|
|
end function
|
|
|
|
constant tests = {{3, 2, 6, 4, 5, 1},
|
|
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}}
|
|
for i=1 to length(tests) do
|
|
?lis(tests[i])
|
|
end for
|