Definition:
A sequence is called "Palindrome" if it is read same left to right and right to left. The sequence remains same as before after reversing it. The sequence "MADAM" is a Palindrome.
More about Palindrome.
A sequence which is a Palindrome is called a Palindromic Sequence. In this problem, given any sequence (not necessarily palindromic sequence), and we have to determine the Longest Palindromic Sub-sequence of Maximum Length of Palindrome of it.
A dynamic approach is not mandatory for this problem, because there is no overlapping sub-problems and so no optimal sub-structure available for Longest Palindromic Sub-sequence.
But if we go recursively, it can be easily determined. How? Obviously there is no overlapping sub-problems but we can divide it into sub-problems (that how we do it :p).
Here is a C++ solution for LPS.
Obviously, a memoization make the procedure lot more faster. Here is a memoized faster version.
A sequence is called "Palindrome" if it is read same left to right and right to left. The sequence remains same as before after reversing it. The sequence "MADAM" is a Palindrome.
More about Palindrome.
A sequence which is a Palindrome is called a Palindromic Sequence. In this problem, given any sequence (not necessarily palindromic sequence), and we have to determine the Longest Palindromic Sub-sequence of Maximum Length of Palindrome of it.
A dynamic approach is not mandatory for this problem, because there is no overlapping sub-problems and so no optimal sub-structure available for Longest Palindromic Sub-sequence.
But if we go recursively, it can be easily determined. How? Obviously there is no overlapping sub-problems but we can divide it into sub-problems (that how we do it :p).
Here is a C++ solution for LPS.
#include <iostream>
#include <string>
using namespace std;
template<class T>inline T MAX( T a, T b ){ return a>b ? a:b; } // Note: returns maximum of a and b
string A;
int LPS( int i, int j ) {
if( i == j ) return 1; // A[i] & A[j] are same, cost is 1
if( i > j ) return 0;
if( A[i] == A[j] )
return 2 + LPS( i+1, j-1 ); // A[i] & A[j] are different, cost is 2, 1 for each.
else
return MAX( LPS(i+1, j), LPS(i, j-1) );
}
int main( ){
while( cin >> A ){
int len = A.length( );
int res = LPS(0, len);
cout << "Longest Palindromic Subsequence is: " << res << endl;
}
return 0;
}
Obviously, a memoization make the procedure lot more faster. Here is a memoized faster version.
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
template<class T>inline T MAX( T a, T b ){ return a>b ? a:b; } // Note: returns maximum of a and b
const int SIZ = 105;
#define mset2d(x,n) memset(x,n,sizeof(int [SIZ][SIZ]))
string A;
int memo[SIZ][SIZ];
int LPS( int i, int j ) {
if( i == j ) return 1; // A[i] & A[j] are same, cost is 1
if( i > j ) return 0;
if( memo[i][j] != -1 ) return memo[i][j];
if( A[i] == A[j] )
memo[i][j] = 2 + LPS( i+1, j-1 ); // A[i] & A[j] are different, cost is 2, 1 for each.
else
memo[i][j] = MAX( LPS(i+1, j), LPS(i, j-1) );
return memo[i][j];
}
int main( ){
while( cin >> A ){
mset2d( memo, -1 );
int len = A.length( );
int res = LPS(0, len);
cout << "Longest Palindromic Subsequence is: " << res << endl;
}
return 0;
}
