Solution for longest increasing subsequence using Dynamic Programming technique (DP)

longest_increasing_subsequence.py

sequence = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
n = len(sequence)
lis = [[] for i in range(n)]
lis[0].append(sequence[0])

for x in range(1,n):
    for y in range(x):
        if sequence[x]> sequence[y] and len(lis[x])< len(lis[y])+1:
            lis[x]=lis[y].copy()
    lis[x].append(sequence[x])

k = 1
maxList = lis[0]
for p in lis:
    if len(p) > len(maxList):
        maxList = p
        k = len(p)
print(f'Longest Increasing Subsequence: {maxList}')
print(f'Length: {k}')