function _longest_increasing_subsequence(v::Vector{Int})::Vector{Int}
    M = zeros(Int, length(v))
    P = zeros(Int, length(v))
    Longest = 0
    for i = eachindex(v)
        e = v[i]
        # Find element in sequence so far that is smaller than current element e.
        lo, hi = 1, Longest+1
        while lo < hi
            mid = round(Int, floor((lo+hi)/2))
            if e < v[M[mid]]
                hi = mid
            else
                lo = mid+1
            end
        end
        @assert lo == hi
        P[i] = lo > 1 ? M[lo-1] : -1
        M[lo] = i

        if lo > Longest
            Longest = lo
        end
    end

    @show P, M
    # Reconstruct sequence
    ixs = zeros(Int, 0)
    i = M[Longest]
    while i > 0
        push!(ixs, v[i])
        i = P[i]
    end
    reverse!(ixs)
    ixs
end

function twosum1(a::Vector{Int}, n::Int)::Tuple{Int,Int}
    # n² complexity (trivial):
    for (i,e1) in enumerate(a)
        for (j,e2) in enumerate(a)
            if e1+e2 == n
                return (i,j)
            end
        end
    end
    return (0,0)
end

function twosum2(a::Vector{Int}, n::Int)::Tuple{Int,Int}
    # More clever?
    #
    # 1. sort array; cut off all elements > n. Start from largest leftover number
    # and smallest one; look for a match:
    a_ = sort(a)
    maxix = 1
    for (i, e) = enumerate(a_)
        if e < n
            maxix = i
        else
            break
        end
    end

    a_ = a_[begin:maxix]
    front, back = 1, length(a_)
    while front < back
        while a_[front]+a_[back] < n
            front += 1
        end
        if a_[front]+a_[back] == n
            return (front, back)
        end
        back -= 1
    end
    nothing
end

function watercontainer(a::Vector{Int})
    maxvol = 0
    best = (0,0)
    for lo = 1:length(a)
        for hi = length(a):-1:lo
            vol = (hi-lo) * min(a[lo], a[hi])
            if vol > maxvol
                best = (lo, hi)
                maxvol = vol
            end
        end
    end
    best, maxvol
end

function rainwater(a::Vector{Int})
    lm, rm = 0, 0
    leftmax, rightmax = zeros(Int, length(a)), zeros(Int, length(a))
    for (i,e) in enumerate(a)
        if e > lm
            lm = e
        end
        leftmax[i] = lm
    end
    for (i,e) in enumerate(reverse(a))
        if e > rm
            rm = e
        end
        rightmax[length(rightmax)-(i-1)] = rm
    end

    water = 0
    for (i, e) in enumerate(a)
        water += min(leftmax[i], rightmax[i]) - e
    end
    wat
end

function longest_increasing_subsequence(v::Vector{Int})::Vector{Int}
    M = zeros(Int, length(v)) # M[L] stores last index of sequence with length L.
    P = zeros(Int, length(v)) # P[i] stores predecessor of element i in longest sequence.
    Longest = 0
    for i = eachindex(v)
        # Binary search for position in longest-sequence-so-far
        lo, hi = 1, Longest+1
        while lo < hi
            mid = round(Int, floor((lo+hi)/2))
            if v[i] < v[M[mid]]
                hi = mid
            else
                lo = mid+1
            end
        end
        @assert lo == hi
        # Update predecessor of current index.
        P[i] = lo > 1 ? M[lo-1] : -1
        M[lo] = i

        if lo >= Longest
            Longest = lo
        end
    end

    # Reconstruct sequence.
    seq = zeros(Int, Longest)
    i = M[Longest]
    for j = Longest:-1:1
        seq[j] = v[i]
        i = P[i]
    end
    seq
end

function longest_common_subsequence(x::Vector{T}, y::Vector{T})::Vector{T} where {T}
    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
    for i = 1:m
        for j = 1:n
            if x[i] == y[j]
                C[i+1,j+1] = C[i, j] + 1
            else
                C[i+1,j+1] = max(C[i, j+1], C[i+1, j])
            end
        end
    end

    # Reconstruct sequence
    i, j = m, n
    k = C[m+1, n+1]
    seq = Vector{T}(undef, k)
    while k > 0
        if C[i,j] + 1 == C[i+1,j+1]
            seq[k] = x[i]
            k -= 1
            i -= 1
            j -= 1
        elseif C[i,j+1] == C[i+1,j+1]
            i -= 1
        elseif C[i+1,j] == C[i+1,j+1]
            j -= 1
        end
    end
    seq
end

function lcss_slow_memoize(a::AbstractArray{T}, b::AbstractArray{T};
    d::Matrix=fill(0, length(a), length(b)),
    c::Vector{Vector{T}}=Vector{Vector{T}}())::Vector{T} where {T}

    if 0 == min(length(a), length(b))
        return []
    end
    ck = (length(a), length(b))
    if d[ck...] > 0
        return c[d[ck...]]
    end
    nexts = [lcss_slow_memoize((@view a[i:end]), (@view b[j:end]); d=d, c=c) for i = 2:length(a) for j = 1:length(b)]
    longest = isempty(nexts) ? [] : nexts[findmax(length, nexts)[2]]
    if a[begin] == b[begin]
        r = vcat([a[begin]], longest)
        push!(c, r)
        d[length(a),length(b)] = length(c)
        return r
    else
        push!(c, longest)
        d[length(a),length(b)] = length(c)
        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

function max_stock_profit(prices::AbstractArray{<:Real})::Real
    start = prices[1]
    i = 2
    profit = 0
    while i <= length(prices)
        if prices[i] >= prices[i-1]
            i += 1
        else
            profit += prices[i-1] - start
            start = prices[i]
            i += 1
        end
    end
    profit += prices[end] - start
    profit
end

function sort_swapped(a::AbstractArray)
    count = 0
    first, second = 0, 0
    for i = eachindex(a)
        if i <= 1
            continue
        end
        if count == 0
            if a[i] < a[i-1]
                first = i-1
                count += 1
            end
        else
            if a[i] < a[i-1]
                second = i
                count += 1
                break
            end
        end
    end
    if second == 0
        second = first+1
    end
    a[first], a[second] = a[second], a[first]
    a
end

function max_sum_subarray(a::AbstractArray)

    max_encountered = -10000
    current_sum = 0
    lo, hi = 1, length(a)

    for (i, e) = enumerate(a)
        if e > current_sum+e
            lo = i
        end
        current_sum = max(current_sum+e, e)
        if current_sum >= max_encountered
            hi = i
        end
        max_encountered = max(max_encountered, current_sum)
    end
    max_encountered
end