dp

longest_2x.py

def longest_exp_inc_seq(a):
    """
    >>> longest_exp_inc_seq([0, 4, 8, 2, 1, 3, 7, 15, 2, 9, 7])
    [0, 1, 3, 7, 15]
    """
    if len(a) == 0:
        return a

    s = [1] * len(a)    # the longest subsequence that ends at i
    p = [-1] * len(a)   # the index of the previous element in the longest subsequence at i
    max_idx = 0
    for i in range(1, len(a)):
        for j in range(0, i):
            if a[i] > a[j] * 2 and s[j] + 1 > s[i]: # s[i] = max(1, s[j] + 1)
                s[i] = s[j] + 1
                p[i] = j
        if s[i] > s[max_idx]:
            max_idx = i

    max_len = s[max_idx]
    ret = [0] * max_len
    i = 1
    while max_len > 0:
        ret[-i] = a[max_idx]
        max_idx = p[max_idx]
        i += 1
        max_len -= 1
    return ret