Longest palindromic subsequence by memoization

I've written some code to solve the longest palindromic subsequence problem.

def memoize(f):
    """ Function decorator used to cache results """
    d = dict()
    def inner(*args):
        if args not in d:
            d[args] = f(*args)
        return d[args]
    return inner

def max_palindrome(s):
    """ Returns the longest length palindrome that can
        be generated from s

    >>> max_palindrome("BBABCBCAB")
    7
    """

    @memoize
    def inner(s):
        if len(s) == 1:
            return 1
        if s[0] == s[-1]:
            return 2 + inner(s[1:-1])
        return max(inner(s[1:]), inner(s[:-1]))
    return inner(s)

My solution uses memoization to improve performance. I'm wondering how my code can be improved to return the longest subsequence rather than just the longest length achievable from the input characters.

The simplistic answer, possibly not the most efficient answer, is simply to build a tuple result of the length, and the string, and then memoize that one.

When trying with longer strings, it turns out that your version of the recursive version from the link is not complete. You didn't handle the len(s) == 2 case which led to index errors. With that fixed, and the tuple returns, the code now looks like:

def max_palindrome(s):
    """ Returns the longest length palindrome that can
        be generated from s

    >>> max_palindrome("BBABCBCAB")
    (7, "BACBCAB")[1] -> BACBCAB
    """

    @memoize
    def inner(s):

        if len(s) == 1:
            return 1, s

        if s[0] != s[-1]:
            _, recursed = max(inner(s[1:]), inner(s[:-1]))
            return len(recursed), recursed

        elif s[0] == s[-1]:

            if len(s) == 2:
                return 2, s
            else:
                new_text = '{0}{1}{0}'.format(s[0], inner(s[1:-1])[1])
                return len(new_text), new_text

    return inner(s)[1]

You could also improve your code by commenting a little more, and giving some proper names instead of single character variables, which are usually reserverd for loops.

Addendum: Faulty algorithm

The suggested algorithm from your link, doesn't explore all possibilities available. Neither lengthwise, nor is all combinations covered. The following two test cases prove they are faulty:

print max_palindrome("abcABCBAabc")  # (7, 'cABCBAc')
print max_palindrome("abcABCBAcba")  # (11, 'abcABCBAcba')

Both of these should return the latter, if all combinations had been considered. This simple test run was done without memoization, which could introduce other faults. Did also test with the same strings in the online code generator linked from your proposed link.

Not that your link also states that you can rebuild the characters any way you like, whilst a more normal version is that the palindrome string must be displayed within the string itself. I.e. your links says that in the string "BBABCBCAB", all of the following are palindromes: "BACBCAB", "BBCBB", and "BBBBB". Neither of these are substrings.

Wikipedia has the more normal definition of longest palindromic substring and here is a Stack Overflow answer with links to two implementations of Manacher's algorithm.

StackExchange Code Review Q#109562, answer score: 4