43 lines
999 B
Text
43 lines
999 B
Text
require "table2"
|
|
|
|
local function longest_increasing_subsequence(x)
|
|
local n = #x
|
|
if n == 0 then return {} end
|
|
if n == 1 then return x end
|
|
local p = table.rep(n, 0)
|
|
local m = table.rep(n, 0)
|
|
local len = 0
|
|
for i = 1, n do
|
|
local lo = 1
|
|
local hi = len
|
|
while lo <= hi do
|
|
local mid = math.ceil((lo + hi) / 2)
|
|
if x[m[mid]] < x[i] then
|
|
lo = mid + 1
|
|
else
|
|
hi = mid - 1
|
|
end
|
|
end
|
|
if lo > 1 then p[i] = m[lo - 1] end
|
|
m[lo] = i
|
|
if lo > len then len = lo end
|
|
end
|
|
local res = table.rep(len, 0)
|
|
if len > 0 then
|
|
local k = m[len]
|
|
for i = len, 1, -1 do
|
|
res[i] = x[k]
|
|
k = p[k]
|
|
end
|
|
end
|
|
return res
|
|
end
|
|
|
|
local lists = {
|
|
{3, 2, 6, 4, 5, 1},
|
|
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
|
|
}
|
|
|
|
lists:foreach(|l| -> do
|
|
print(longest_increasing_subsequence(l):concat(", "))
|
|
end)
|