A palinadrome is a nonempty string that reads the same forward and backward across some alphabet. Palindromes include all strings of length one, civic, racecar, and aibohphobia (fear of palindromes). Provide an efficient approach for determining the longest palindrome that is a subsequence of the supplied input string. Given the input "character," your algorithm should return "caac."
I now understand how to calculate the length of the result. How can I obtain the result sequence? I'm checking all 2n combinations; according to this source, it's the least efficient algorithm, and it recommends using a dynamic program to solve this problem in O(n2), is that correct?
def mylongest(self, i, j): if j - i <= 1: return j-i else: if self.sequence[i] == self.sequence[j]: return self.mylongest(i+1,j-1) + 2 else: return max (self.mylongest(i+1, j), self.mylongest(i, j-1))