Lua最长递增子序列：贪心加二分的线性优化

local function lis(t)
    local n = #t
    local dp = {}
    local best = 0
    for i = 1, n do
        dp[i] = 1
        for j = 1, i - 1 do
            if t[j] < t[i] then
                dp[i] = math.max(dp[i], dp[j] + 1)   -- 平方级
            end
        end
        best = math.max(best, dp[i])
    end
    return best
end

local function lis(t)
    local tails = {}
    for _, v in ipairs(t) do
        local lo, hi = 1, #tails
        while lo <= hi do
            local mid = math.floor((lo + hi) / 2)
            if tails[mid] < v then lo = mid + 1
            else hi = mid - 1 end
        end
        tails[lo] = v               -- 二分定位替换
    end
    return #tails
end
sendmsg(actor, 1, "最长递增子序列长度 "
    .. lis({3, 1, 2, 1, 8, 5, 6}))