def print_LCS(b,X,i,j):
    if i==0 and j==0:
        return
    if b[i][j]=='diagonal':
        print_LCS(b,X,i-1,j-1)
        print (X[i])
    elif b[i][j]== 'up':
        print_LCS(b,X,i-1,j)
    else: print_LCS(b,X,i,j-1)

def LMIS_Length(X):
    n = len(X)
    cache=[[0 for _ in range(0,n+1)] for _ in range(0,n+1)]
    b=[[0 for _ in range(n)]for _ in range(n)]
    for i in range(1,n):
        for j in range(1,i):
            if X[i]>X[j]:
                cache[i][j]=cache[i-1][j-1]+1
                b[i][j]='diagonal'
            elif cache[i][j]>=cache[i-1][j]:
                cache[i][j]=cache[i-1][j]
                b[i][j]='up'
            else:
                cache[i][j]=cache[i][j-1]
                b[i][j]='left'
    return (cache, print_LCS(b,X,n-1,n-1))


lst=[1,3,5,4,8,2,9,4,10]
LMIS_Length(lst)
#print_LCS(LMIS_Length(lst)[1],lst,)