Whoops, Slyphon was doing LIS not LCS

lis.py

#!/usr/bin/env python3

def lis_recursive(numbers, limit=0):

    if not numbers:
        return []
    else:
        n, *rest = numbers

        if n >= limit:
            a = [n] + lis_recursive(rest, n)
            b = lis_recursive(rest, limit)
            return max(a, b, key=lambda x: len(x))
        else:
            return lis_recursive(rest, limit)

def lis_dp(numbers):

    # matrix[i][j] is lis for tail starting at index i with limit numbers[j]

    matrix = [ [ None for _ in numbers ] for _ in numbers ] + [ [ [] for _ in numbers ] ]

    indices = range(len(numbers))

    for i in reversed(indices):
        for j in indices:
            n = numbers[i]
            limit = numbers[j]
            if n >= limit:
                a = [n] + matrix[i+1][i]
                b = matrix[i+1][j]
                matrix[i][j] = max(a, b, key=lambda x: len(x))
            else:
                matrix[i][j] = matrix[i+1][j]

    return matrix[0][0]


def lis_dp2(numbers):

    # Note that in the previous version, we only ever access two rows
    # of the matrix per iteration of the outer loop.

    current  = [ None for _ in numbers ]
    filled = [ [] for _ in numbers ]

    indices = range(len(numbers))

    for i in reversed(indices):
        for j in indices:
            n = numbers[i]
            limit = numbers[j]
            if n >= limit:
                a = [n] + filled[i]
                b = filled[j]
                current[j] = max(a, b, key=lambda x: len(x))
            else:
                current[j] = filled[j]
        current, filled = filled, current

    return filled[0]

if __name__ == '__main__':

    print(lis_recursive([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]))
    print(lis_dp([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]))
    print(lis_dp2([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]))