Longest Increasing Sequence DFS

Longest Increasing Sequence DFS

def longest_increasing_subsequence_dfs(lst):
    lis_seq = []
    sz = len(lst)
    def lis(index,seq):
        if len(seq) + (sz - index) < len(lis_seq): return #prune the rest.
        for i in xrange(index,sz):
            if seq[-1] < lst[i]:
                seq.append(lst[i])
                lis(i+1,seq)
                seq.pop()
        else:
            if len(seq) > len(lis_seq):
                l = lis_seq
                l[:] = seq
    for i in xrange(sz):
        lis(i + 1,[lst[i]])
    return lis_seq