#include <iostream>

using namespace std;

int lps(string seq, int i, int j) {

int len1, len2;

if (i == j)//当i=j时，则此时扫描到的项是一定可以放入该回文子序列中并且对回文子序列的长度贡献为1

return ;

if (i > j)//当i>j时，即扫描到的左边的数在右边已经扫描过了，所以该项及往后的所有项都是已经扫描过的项，对回文子序列的长度贡献为0

return ;

if (seq[i] == seq[j])//当扫描到相同的字符时

return lps(seq, i + , j - ) + ;//此时这两个相同字符必定可以放入回文子序列中，故总计对回文子序列的长度贡献为2

len1 = lps(seq, i, j - );//如果没有扫描到相同字符，则此时有两种情况，一种是此时的第i个字符对最长回文子序列的长度有贡献

len2 = lps(seq, i + , j);//另一种是此时的第j个字符对最长回文子序列的长度有贡献

if (len1 > len2)//比较上面两种情况的回文子序列的长度大小，返回其中长度较大的回文子序列的长度

return len1;

return len2;

}

int main() {

string seq = "acmerandacm";//给出字符串

int n = seq.size();//统计字符串的长度

cout << lps(seq, , n - ) << endl;//计算最长回文子序列

return ;

}