Problem: Given a sequence, find the length of the longest palindromic sub-sequence in it.
Longest Common Sub-sequence can be used to solve this problem. The steps are as follows:
1. Reverse the given sequence and store the reverse in another array say reverse[0..n-1]
2) LCS of the given sequence and reverse will be the longest palindromic sequence
int LPS(std::string S)
std::string T = S;
return LCS(S, T);
Please find the implementation of LCS at the following URL: