这一类的问题可以使用动态规划的方法去做，我之前应该有几篇博文都是关于回文序列的求解的，正好有可以复用的代码就懒得再用别的方法写了，直接套用，思想还是滑窗切片，很简单就是运算会多点，下面是具体实现：

#!usr/bin/env python
#encoding:utf-8

'''
__Author__:沂水寒城
功能：寻找最长回文子序列
'''

def slice_window(one_str,w=1):
    '''
    滑窗函数
    '''
    res_list=[]
    for i in range(0,len(one_str)-w+1):
        res_list.append(one_str[i:i+w])
    return res_list


def is_huiwen(one_str_list):  
    '''
    输入一个字符串列表，判断是否为回文序列 
    '''  
    if len(one_str_list)==1:  
        return True   
    else:  
        half=len(one_str_list)/2  
        if len(one_str_list)%2==0:  
            first_list=one_str_list[:half]  
            second_list=one_str_list[half:]  
        else:  
            first_list=one_str_list[:half]  
            second_list=one_str_list[half+1:]  
        if first_list==second_list[::-1]:  
            return True   
        else:  
            return False  


def find_longest_sub_palindrome_str(one_str):
    '''
    主函数,寻找最长回文子序列
    '''
    all_sub=[]
    for i in range(1,len(one_str)):
        all_sub+=slice_window(one_str,i)
    all_sub.append(one_str)
    new_list=[]
    for one in all_sub:
        if is_huiwen(list(one)):
            new_list.append(one)
    new_list.sort(lambda x,y:cmp(len(x),len(y)),reverse=True)
    print new_list[0]


if __name__ == '__main__':
    one_str_list=['uabcdcbaop','abcba','dmfdkgbbfdlg','mnfkabcbadk']
    for one_str in one_str_list:
        find_longest_sub_palindrome_str(one_str)

结果如下：

abcdcba
abcba
bb
abcba
[Finished in 0.3s]