--- a/julia/longest_increasing_subsequence.jl	Tue Feb 14 23:41:19 2023 +0100
+++ b/julia/longest_increasing_subsequence.jl	Wed Feb 15 22:46:38 2023 +0100
@@ -32,3 +32,60 @@
     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