Mercurial > lbo > hg > juliaplay
view julia/arrays.jl @ 6:661876a2502e
py: dp
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 19 Feb 2023 12:50:44 +0100 |
parents | 00f57653128a |
children | cb419167dcb3 |
line wrap: on
line source
function _longest_increasing_subsequence(v::Vector{Int})::Vector{Int} M = zeros(Int, length(v)) P = zeros(Int, length(v)) Longest = 0 for i = eachindex(v) e = v[i] # Find element in sequence so far that is smaller than current element e. lo, hi = 1, Longest+1 while lo < hi mid = round(Int, floor((lo+hi)/2)) if e < v[M[mid]] hi = mid else lo = mid+1 end end @assert lo == hi P[i] = lo > 1 ? M[lo-1] : -1 M[lo] = i if lo > Longest Longest = lo end end @show P, M # Reconstruct sequence ixs = zeros(Int, 0) i = M[Longest] while i > 0 push!(ixs, v[i]) i = P[i] end reverse!(ixs) ixs end function twosum1(a::Vector{Int}, n::Int)::Tuple{Int,Int} # n² complexity (trivial): for (i,e1) in enumerate(a) for (j,e2) in enumerate(a) if e1+e2 == n return (i,j) end end end return (0,0) end function twosum2(a::Vector{Int}, n::Int)::Tuple{Int,Int} # More clever? # # 1. sort array; cut off all elements > n. Start from largest leftover number # and smallest one; look for a match: a_ = sort(a) maxix = 1 for (i, e) = enumerate(a_) if e < n maxix = i else break end end a_ = a_[begin:maxix] front, back = 1, length(a_) while front < back while a_[front]+a_[back] < n front += 1 end if a_[front]+a_[back] == n return (front, back) end back -= 1 end nothing end function watercontainer(a::Vector{Int}) maxvol = 0 best = (0,0) for lo = 1:length(a) for hi = length(a):-1:lo vol = (hi-lo) * min(a[lo], a[hi]) if vol > maxvol best = (lo, hi) maxvol = vol end end end best, maxvol end function rainwater(a::Vector{Int}) lm, rm = 0, 0 leftmax, rightmax = zeros(Int, length(a)), zeros(Int, length(a)) for (i,e) in enumerate(a) if e > lm lm = e end leftmax[i] = lm end for (i,e) in enumerate(reverse(a)) if e > rm rm = e end rightmax[length(rightmax)-(i-1)] = rm end water = 0 for (i, e) in enumerate(a) water += min(leftmax[i], rightmax[i]) - e end wat end 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 longest_common_subsequence(x::Vector{T}, y::Vector{T})::Vector{T} where {T} m, n = length(x), length(y) C = zeros(Int, m+1, n+1) # Not necessary: for i = 1:m C[i,1] = 0 end for j = 1:n C[1,j] = 0 end for i = 1:m for j = 1:n if x[i] == y[j] C[i+1,j+1] = C[i, j] + 1 else C[i+1,j+1] = max(C[i, j+1], C[i+1, j]) end end end # Reconstruct sequence i, j = m, n k = C[m+1, n+1] seq = Vector{T}(undef, k) while k > 0 if C[i,j] + 1 == C[i+1,j+1] seq[k] = x[i] k -= 1 i -= 1 j -= 1 elseif C[i,j+1] == C[i+1,j+1] i -= 1 elseif C[i+1,j] == C[i+1,j+1] j -= 1 end end seq end function lcss_slow_memoize(a::AbstractArray{T}, b::AbstractArray{T}; d::Matrix=fill(0, length(a), length(b)), c::Vector{Vector{T}}=Vector{Vector{T}}())::Vector{T} where {T} if 0 == min(length(a), length(b)) return [] end ck = (length(a), length(b)) if d[ck...] > 0 return c[d[ck...]] end nexts = [lcss_slow_memoize((@view a[i:end]), (@view b[j:end]); d=d, c=c) for i = 2:length(a) for j = 1:length(b)] longest = isempty(nexts) ? [] : nexts[findmax(length, nexts)[2]] if a[begin] == b[begin] r = vcat([a[begin]], longest) push!(c, r) d[length(a),length(b)] = length(c) return r else push!(c, longest) d[length(a),length(b)] = length(c) return longest end end