Longest Increasing Subsequence.

def longestIncreasingSubsequence(sequence):

    n = len(sequence)

    dp = [1] * n

    prev = [-1] * n

    for i in range(1, n):

        for j in range(i):

            if sequence[i] > sequence[j] and dp[i] < dp[j] + 1:

                dp[i] = dp[j] + 1

                prev[i] = j

    max_length = max(dp)

    lis = []

    idx = dp.index(max_length)

    while idx != -1:

        lis.append(sequence[idx])

        idx = prev[idx]

    lis.reverse()

    return lis

sequence = [1, 10, 5, 20, 15, 10, 30, 49, 25, 35, 66, 75, 44]

lis = longestIncreasingSubsequence(sequence)

print("Longest Increasing Subsequence:", lis)