A sequence is a palindrome if it is the same backwords andforwards. Suppose you

Question

A sequence is a palindrome if it is the same backwords andforwards. Suppose you are given a sequence of characters, forexample "datastructuresisfun". There are many subsequences of thisstring which are palindromes. For example, the subsequence "sruurs"is a palindrome. For a given sequence, design an algorithm tocompute the length of the longest subsequence that is a palindrome.That is, solve the following problem: Input     *A sequence of characters X =x1,x2,...,xn                                   Output   *The length of the longest subsequence of X thatis a palindrome. A sequence is a palindrome if it is the same backwords andforwards. Suppose you are given a sequence of characters, forexample "datastructuresisfun". There are many subsequences of thisstring which are palindromes. For example, the subsequence "sruurs"is a palindrome. For a given sequence, design an algorithm tocompute the length of the longest subsequence that is a palindrome.That is, solve the following problem: Input     *A sequence of characters X =x1,x2,...,xn                                   Output   *The length of the longest subsequence of X thatis a palindrome.                                   Output   *The length of the longest subsequence of X thatis a palindrome.

Explanation / Answer

This should get you started. I can't guarantee correctness as Ididn't test it thoroughly. I also left for you to find an algorithmto determine if each sub-string is a palindrome(i.e. is_palindromefunction) Some searches on the internet should prove fruitful.
Basically examine all possibly sub-strings to determine ifit’s a palindrome and keep track of the max length found.

Given array X with elements X1 through Xn where n = length ofthe string.

Examine the string backwards and determine if each successivestring is a palindrome.

Use two loops to examine all substrings.

Max_palindrome (X[x1…xn])

maxpal = 0; // length of max palindrome found

for(cur=n; cur > 1; cur--) // loop through allsubstrings beginning at cur and working backwards

for (i=0; i < n; i++) // look atthe string from n to i

               if ( is_palindrome(Xn-i…Xn ) ) // if the examined substringis a palindrome

                               find length of Xi-n through Xn // find its length and compareto max value

                               and compare to maxpal.

                               If (max_pal < length of Xi-n through Xn)

                                               Maxpal = length of Xi-n through Xn

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.