Mercurial > lbo > hg > juliaplay
view longest_increasing_subsequence.jl @ 2:b7160d5e22cc
Add longest common/increasing subsequence algorithms
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 12 Feb 2023 21:06:13 +0100 |
parents | |
children |
line wrap: on
line source
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