Mercurial > lbo > hg > juliaplay
changeset 21:4b24b380679d
Max. sum of increasing subsequence
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Thu, 02 Mar 2023 20:48:26 +0100 |
parents | 9a9329349f98 |
children | cbb6e979bbd5 |
files | julia/dp.jl |
diffstat | 1 files changed, 36 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/julia/dp.jl Thu Mar 02 20:32:28 2023 +0100 +++ b/julia/dp.jl Thu Mar 02 20:48:26 2023 +0100 @@ -343,3 +343,39 @@ min(case_a, case_b, case_c) end +function max_sum_liss(v::AbstractVector{<:Integer}, i=1, last=v[begin], s=0)::Int + if i == length(v) + return s + else + if v[i] >= last + incl = max_sum_liss(v, i+1, v[i], s+v[i]) + excl = max_sum_liss(v, i+1, last, s) + return max(incl, excl) + else + start_new = max_sum_liss(v, i+1, v[i], v[i]) + continue_old = max_sum_liss(v, i+1, last, s) + return max(start_new, continue_old) + end + end +end + +"""This doesn't work. Why? + +Only returning the max-sum is not enough. We lack the ability to communicate +a broken sequence to calls down-stack. +""" +function max_sum_liss_2(v::AbstractVector{<:Integer}, i=1, last=v[begin]) + if i > length(v) + return 0 + else + if v[i] >= last + incl = v[i] + max_sum_liss_2(v, i+1, v[i]) + excl = max_sum_liss_2(v, i+1, last) + max(incl, excl) + else + start_new = v[i] + max_sum_liss_2(v, i+1, v[i]) + cont_old = max_sum_liss_2(v, i+1, last) + max(start_new, cont_old) + end + end +end