Skip to content

Instantly share code, notes, and snippets.

@dermesser

dermesser/liss.jl

Last active February 28, 2023 12:44
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save dermesser/739253b288a2ef19d382b1215e450d39 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save dermesser/739253b288a2ef19d382b1215e450d39 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. dermesser revised this gist Feb 28, 2023. 1 changed file with 42 additions and 1 deletion.
    43 changes: 42 additions & 1 deletion liss.jl
    View file
    Original file line number Diff line number Diff line change
    @@ -31,4 +31,45 @@ function longest_increasing_subsequence(v::Vector{Int})::Vector{Int}
    i = P[i]
    end
    seq
    end
    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
  2. dermesser created this gist Nov 13, 2022.
    34 changes: 34 additions & 0 deletions liss.jl
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,34 @@
    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