Mercurial > lbo > hg > juliaplay
changeset 12:cb419167dcb3
Some DP exercises in julia
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Mon, 20 Feb 2023 23:12:58 +0100 |
parents | ffb42007e4de |
children | 55c9d0026123 |
files | julia/arrays.jl julia/longest_common_subsequence.jl |
diffstat | 2 files changed, 80 insertions(+), 6 deletions(-) [+] |
line wrap: on
line diff
--- a/julia/arrays.jl Sun Feb 19 19:20:34 2023 +0100 +++ b/julia/arrays.jl Mon Feb 20 23:12:58 2023 +0100 @@ -212,3 +212,80 @@ return longest end end + +function longest_consecutive_subarray(a::AbstractArray{<:Integer}) + isdistinctonly(s) = length(Set(s)) == length(s) + + L = -1 + lix = nothing + for i = 1:length(a) + for j = i+1:length(a) + v = @view a[i:j] + if isdistinctonly(v) && maximum(v) - minimum(v) == (j-i) && (j-i+1) > L + L = j-i+1 + lix = (i, j) + end + end + end +end + +function replace_every_element_with_product_of_every_other_element(a::AbstractArray{<:Integer}) + p = prod(a) + + [p/ae for ae = a] +end + +function max_positive_difference(a::AbstractArray{<:Real}) + D = -1 + ix = nothing + for i = eachindex(a) + for j = i:length(a) + if a[i] <= a[j] && a[j] - a[i] > D + ix = (i, j) + D = a[j] - a[i] + end + end + end + @show (D, ix) +end + +function max_product_subarray(a::AbstractArray{<:Integer}) + + lo, hi = -abs(prod(a)), abs(prod(a)) + highest = lo + + for i = eachindex(a) + lo_ = lo + lo = min(a[i], min(lo * a[i], hi * a[i])) + hi = max(a[i], max(hi * a[i], lo_ * a[i])) + highest = max(hi, highest) + end + + highest +end + +function longest_continuous_common_sum(x::AbstractArray{Bool}, y::AbstractArray{Bool}) + xs = zeros(Int, size(x)) + ys = zeros(Int, size(y)) + + xs[1] = x[1] + ys[1] = y[1] + for i = 2:length(x) + xs[i] = xs[i-1] + x[i] + ys[i] = ys[i-1] + y[i] + end + + cl = min(length(x), length(y)) + L = 0 + @show (xs, ys) + for i = 1:cl + for j = i+1:cl + xsum = xs[j]-xs[i] + ysum = ys[j]-ys[i] + if xsum == ysum + L = max(L, j-i+1) + end + end + end + L +end
--- a/julia/longest_common_subsequence.jl Sun Feb 19 19:20:34 2023 +0100 +++ b/julia/longest_common_subsequence.jl Mon Feb 20 23:12:58 2023 +0100 @@ -48,12 +48,8 @@ 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 + C[:,1] .= 0 + C[1,:] .= 0 for i = 1:m for j = 1:n if x[i] == y[j] @@ -64,6 +60,7 @@ end end + display(C) # Reconstruct sequence i, j = m, n k = C[m+1, n+1]