Longest Increasing Subsequence DP

Longest Increasing Subsequence DP

def longest_increasing_subsequence_dp(lst):
    if not lst: return None
    lis_len = []
    prev = []

    for i,v in enumerate(lst):
        mx = 0
        mxi = -1
        for j in xrange(i):
            if v > lst[j] and mx < lis_len[j]: #can v extend the current longest increasing subsequence?
                mx = lis_len[j]
                mxi = j
        lis_len.append(1 + mx)
        prev.append(mxi)

    index = max(xrange(len(lst)),key=lis_len.__getitem__)
    lis = []
    while index >= 0: # go backwards till index < 0
        lis.append(lst[index])
        index = prev[index] 
    lis.reverse()
    return lis