view julia/coins.jl @ 6:661876a2502e

py: dp
author Lewin Bormann <lbo@spheniscida.de>
date Sun, 19 Feb 2023 12:50:44 +0100
parents c1db337c15be
children
line wrap: on
line source


function best_selection(a::Vector{UInt})::Tuple{Int, Int, Int, Vector{UInt}}
    N = length(a)
    N_2 = div(N, 2)
    left, right = 1, N_2
    current_sum = sum(a[left:right])
    min = current_sum
    for i in 1:N_2
        current_sum -= a[i]
        current_sum += a[i+N_2]
        if current_sum <= min
            min = current_sum
            left, right = i+1, i+N_2
        end
    end
    (min, left, right, a[left:right])
end