Dynamic Programming
This yields the following algorithm
1 2 3 4 5 6 7 8 9  int LPS(char* str, int a, int b) { if (a > b) return 0;
if (a == b) return 1;
if (str[a] == str[b]) return LPS(str, a+1, b1) + 2 ;
return max(LPS(str, a+1, b), LPS(str, a, b1)); }

// Returns the length of the longest palindromic subsequence in seq
int
lps(
char
*seq,
int
i,
int
j)
{
// Base Case 1: If there is only 1 character
if
(i == j)
return
1;
// Base Case 2: 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, j1) + 2;
// If the first and last characters do not match
return
max( lps(seq, i, j1), lps(seq, i+1, j) );
}
/* Driver program to test above functions */ int main() { char seq[] = "GEEKS FOR GEEKS" ; int n = strlen (seq); printf ( "The length of the LPS is %d" , lps(seq)); getchar (); return 0; }

Output:
The length of the LPS is 7
Comments
Post a Comment