Longest Palindromic Subsequence

int lps(char *seq, int i, int j) // i and j are first and last character
{
   // If there is only 1 character
   if (i == j)
     return 1;
 
   // If there are only 2 characters and both are same
   if (seq[i] == seq[j] && i + 1 == j)
     return 2;
 
   // If the first and last characters match
   if (seq[i] == seq[j])
      return lps (seq, i+1, j-1) + 2;
 
   // If the first and last characters do not match
   return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}