Mercurial > lbo > hg > juliaplay
view julia/longest_increasing_subsequence.jl @ 40:5e3662b65004 default tip
Land/water find peak problem
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Mon, 03 Apr 2023 22:04:42 +0200 |
parents | 1ae2e0c2ea18 |
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 function sort_by_length!(v::Vector{Vector{T}}) where {T} sort!(v; rev=true, by=length) end function liss2(v::AbstractArray{T}, st::Vector{Vector{T}}=Vector{T}[])::Vector where {T} init = isempty(st) if length(v) <= 1 push!(st, collect(v)) elseif length(v) == 2 if v[1] < v[2] push!(st, collect(v)) else push!(st, [v[1]], [v[2]]) end else liss2((@view v[begin+1:end]), st) sort_by_length!(st) for s = st if v[begin] < s[begin] push!(st, vcat(v[begin], s)) end end push!(st, [v[begin]]) end if init sort_by_length!(st) end st end function liss3(v::AbstractArray{T}) where {T} L = zeros(Int, length(v)) prevs = zeros(Int, length(v)) findprevel(val, i) = findlast(e -> e > 0 && v[e] < val, (@view L[begin:i])) longest = 0 for i = eachindex(v) p = findprevel(v[i], i) if isnothing(p) L[1] = i else prevs[i] = L[p] L[p+1] = i longest = max(longest, p+1) end end # Reconstruct vs = zeros(T, longest) e = L[longest] for i = longest:-1:1 vs[i] = v[e] e = prevs[e] end vs end