Longest Increasing Subsequence

In [11]:

    

def lis(l_in):
    l = [0] * len(l_in)
    
    l[0] = 1
    
    for i in range(1, len(l)):
        qualifying = [
            l[j]
            for j in range(i)
            if l_in[j] < l_in[i]
        ]
        # print(i, qualifying, l)
        l[i] = 1 + (max(qualifying) if len(qualifying) > 0 else 0)
        
    return max(l)


    

In [12]:

    

lis([5, 2, 8, 6, 3, 6, 9, 7]) == 4


    

    
Out[12]:





True