Longest Palindromic Subsequence or Maximum Length of Palindrome

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.

#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;
}