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]