#!/usr/bin/env python3

# Author: Leonardo Tamiano

def max_palindrome_sub_string(seq):
    """
    Returns the length of the longest palindrome substring in seq

    :param <string> seq: sequence of characters
    :return <int>: length of the longest palindrome substring in seq
    """

    n = len(seq)
    opt = [[0 for _ in range(0, n)] for _ in range(0, n)]

    for i in range(0, n):
        opt[i][i] = 1

    for l in range(1, n):
        for i in range(0, n - l):
            j = i + l
            if seq[i] == seq[j] and opt[i+1][j-1] == (j - i - 1):
                opt[i][j] = j - i + 1
            else:
                opt[i][j] = max([opt[i+1][j], opt[i][j-1], opt[i+1][j-1]])
                
    return opt[0][n-1]


def max_palindrome_sub_sequence(seq):
    """
    computes the longest palindrome sub_sequence in seq
    :param seq: string of characters
    :return: longest palindrome sub_sequence of seq
    """
    n = len(seq)
    opt = [[0 for _ in range(0, n)] for x in range(0, n)]

    for i in range(0, n):
        opt[i][i] = 1

    for l in range(1, n):
        for i in range(0, n - l):
            j = i + l
            if seq[i] == seq[j]:
                opt[i][j] = 2 + opt[i+1][j-1]
            else:
                opt[i][j] = max(opt[i+1][j], opt[i][j-1])

    return generate_palindrome(seq, opt, 0, n-1)


def generate_palindrome(seq, opt, i, j):
    """
    Generate the longest palindrome sub_sequence in seq[i:j+1], using the previously computed
    dynamic table opt

    :param seq: string of characters
    :param opt: dynamic table opt, satisfying opt[i][j] := length of the longest sub_sequences in seq[i][j+1]
    :param i: left-most index
    :param j: right-most index
    :return <string>: longest palindrome sub_sequence in seq[i:j+1]
    """
    if i > j:
        return ""
    elif seq[i] == seq[j]:
        return seq[i] + generate_palindrome(seq, opt, i+1, j-1) + seq[j]
    elif opt[i][j] == opt[i+1][j]:
        return generate_palindrome(seq, opt, i+1, j)
    else:
        return generate_palindrome(seq, opt, i, j-1)