Longest Increasing Subsequence

longest_increasing_subsequence.py

def longest_increasing subsequece(arr):
    if arr:
        if len(arr) == 1:
            return 1
        else:
            # memoization              
            p = [1 for i in range(len(arr))]
            for i in range(1, len(arr)):
                for j in range(i):
                    if arr[j] < arr[i]:
                        val = p[j] + 1
                        if val > p[i]:
                            p[i] = val
            return max(p)
    return 0