Standard algorithm for longest increasing subsequence in Julia.

liss.jl

function longest_increasing_subsequence(v::Vector{Int})::Vector{Int}
    M = zeros(Int, length(v)) # M[L] stores last index of sequence with length L.
    P = zeros(Int, length(v)) # P[i] stores predecessor of element i in longest sequence.
    Longest = 0
    for i = eachindex(v)
        # Binary search for position in longest-sequence-so-far
        lo, hi = 1, Longest+1
        while lo < hi
            mid = round(Int, floor((lo+hi)/2))
            if v[i] < v[M[mid]]
                hi = mid
            else
                lo = mid+1
            end
        end
        @assert lo == hi
        # Update predecessor of current index.
        P[i] = lo > 1 ? M[lo-1] : -1
        M[lo] = i

        if lo >= Longest
            Longest = lo
        end
    end

    # Reconstruct sequence.
    seq = zeros(Int, Longest)
    i = M[Longest]
    for j = Longest:-1:1
        seq[j] = v[i]
        i = P[i]
    end
    seq
end

# Alternative, table-free implementation - uses same memory
function recursive_liss(v::AbstractVector{<:Integer})
    N = length(v)
    prev, L = zeros(Int, N), zeros(Int, N)
    Lmax = recursive_liss(v, 1, 1, 0, prev, L)

    # Reconstruct:
    i = L[Lmax]
    l = Lmax
    liss = zeros(Int, Lmax)
    while i > 0
        liss[l] = v[i]
        i = prev[i]
        l -= 1
    end
    liss
end

function recursive_liss(v::AbstractVector{<:Integer}, last=1, i=1, l=0, prev=zeros(Int, length(v)), L=zeros(Int, length(v)), Lmax=[0])::Int
    if i > length(v)
        return l
    else
        if v[i] >= v[last]
            incl = recursive_liss(v, i, i+1, l+1, prev, L, Lmax)
            excl = recursive_liss(v, last, i+1, l, prev, L, Lmax)
            if incl >= excl
                Lmax[1] = max(Lmax[1], incl)
            end
            if incl == Lmax[1]
                L[l+1] = i
                prev[i] = last
            end
            max(incl, excl)
        else # v[i] < v[last]
            incl = recursive_liss(v, i, i+1, 1, prev, L, Lmax)
            excl = recursive_liss(v, last, i+1, l, prev, L, Lmax)
            max(incl, excl)
        end
    end
end