5 Maximum Palindrome Subsequence (40 pts) Before solving this problem, you might want to try solving the bonus problem first as a warm-up ezercise to understand palindromes better A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, civic, racecar, noon, and aibohphobia (fear of palindromes) Given a string s, a palindrome subsequence is a subsequence of the characters in s that forms a palindrome. For example, aba and aacaa are palindrome subsequences of the string abracadabra. The first one contains 3 charactes, the second one contains 5 characters. These are not the only palindrome subsequences of abracadabra. For example abaaaba and araaara are also palidrome subsequences of abracadabra and contain 7 characters. In this problem you will find the length of the longest palindrome subsequence of a given string. Design a recursive backtracking algorithm that takes a string as an argument and computes the length of the longest palindrome subsequence. Make your algorithm as simple as possible You may assume that an input string s is given as an array of characters. For example, input string noon is given as an array s[L.4], where s[1] = n, s[2] = o, s[3] o, and s[4 n. Write down the pseudocode and prove that your algorithm is correct. Hint: use induction. No points will be given for an algorithm without the proof. If you are struggling to prove the correctness of your algorithm, chances are it is either too complicated, is incorrect, or both. Try solving the bonus problem first to understand palindromes