Longest Increasing Subsequence

Dynamic.py

def lis_dp(X):
    if not X:
        return 0
    memo = [1] * len(X)
    for i in range(1,len(X)):
        for j in range(i):
            if X[j] < X[i]:
                memo[i] = max(memo[i],memo[j]+1)
    return max(memo)

Naive.py

def lis(X):
    if len(X) == 0:
        return 0
    if len(X) == 1:
        return 1
    maxElement = 0
    for i in range(len(X)):
        maxBefore = lis(X[:i])
        if X[-1] > X[i-1]:
            maxElement = max(maxBefore+1, maxElement)
    return maxElement