Longest increasing subsequence and common substring

I wrote a program that computes longest increasing subsequences and common substrings.

Can you please suggest more elegant and eloquent ways for this program? (Perhaps better ways to represent a graph with vertices and edges?)

Longest increasing subsequences using longest increasing suffixes:

from functools import lru_cache

def maxima(iterable, key=lambda e: e):
    maxima = []
    for e in iterable:
        if not maxima or key(e) == key(maxima[0]):
            maxima.append(e)
        elif key(e) > key(maxima[0]):
            maxima = [e]
    return maxima

def lis(a):
    @lru_cache(maxsize=None)
    def lisuff(i):
        cases = [e + [i]
                 for j in range(i)
                 for e in lisuff(j) 
                 if a[e[-1]] <= a[i]] # 0 <= j < i
        return maxima(cases, key=len) or [[i]]
    z = maxima((e
                for i in range(len(a))
                for e in lisuff(i)), key=len)
    return list(z)

assert [[2, 3, 4], [2, 5, 6]] == lis((7, 8, 1, 5, 6, 2, 3))

Longest common substrings using longest common suffixes:

def lcs(a, b):
    @lru_cache(maxsize=None)
    def lcsuff(i, j): # returns a tuple of (offset, count)
        if i == -1 or j == -1 or a[i] != b[j]:
            return (i, 0)
        o, c = lcsuff(i-1, j-1)
        return (o, c+1) if c > 0 else (i, 1)
    m, n = len(a), len(b)
    z = maxima((lcsuff(i, j) for i in range(m) for j in range(n)), key=lambda e: e[1])
    return [a[s:s+c] for s, c in z]

assert ['aba', 'bab'] == lcs('abab', 'baba')