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