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