20 lines
652 B
Julia
20 lines
652 B
Julia
function lis(arr::Vector{T}) where T
|
|
isempty(arr) && return copy(arr)
|
|
allsequences = Vector{Vector{T}}(undef, length(arr))
|
|
allsequences[begin] = [arr[begin]]
|
|
|
|
for i in firstindex(arr)+1:lastindex(arr)
|
|
nextseq = T[]
|
|
for j in firstindex(arr):i
|
|
if arr[j] < arr[i] && length(allsequences[j]) ≥ length(nextseq)
|
|
nextseq = allsequences[j]
|
|
end
|
|
end
|
|
allsequences[i] = push!(nextseq, arr[i])
|
|
end
|
|
_, idx = findmax(length, allsequences)
|
|
return allsequences[idx]
|
|
end
|
|
|
|
@show lis([3, 2, 6, 4, 5, 1])
|
|
@show lis([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])
|