38 lines
946 B
Text
38 lines
946 B
Text
with javascript_semantics
|
|
function lis(sequence x, integer n = length(x))
|
|
sequence p = repeat(0,n),
|
|
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
|