(phixonline)-->
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