这可以使用动态编程在 O(n^2) 中解决。基本上，问题是关于x[i...j]使用最长子序列构建最长的回文子序列x[i+1...j]，x[i,...j-1]和x[i+1,...,j-1]（如果第一个和最后一个字母相同）。
首先，空字符串和单个字符串通常是回文。请注意，对于子串x[i,...,j]if x[i]==x[j]，我们可以说最长回文的长度是最长回文的长度x[i+1,...,j-1]+2。如果它们不匹配，则最长回文是 和 中的x[i+1,...,j]最大值y[i,...,j-1]。
这给了我们功能：
longest(i,j)= j-i+1 if j-i<=0,
2+longest(i+1,j-1) if x[i]==x[j]
max(longest(i+1,j),longest(i,j-1)) otherwise
您可以简单地实现该函数的记忆版本，或者编写一个自下而上的最长 [i][j] 表。
这只会给你最长子序列的长度，而不是实际的子序列本身。但它也可以很容易地扩展来做到这一点。
这个问题也可以作为一个非常常见的问题的变体来完成，称为 LCS（最长公共子序列）问题。让输入字符串由字符数组 s1[0...n-1] 表示。
1）反转给定的序列并将反转存储在另一个数组中，例如 s2[0..n-1] 本质上是 s1[n-1....0]
2) 给定序列 s1 和反向序列 s2 的 LCS 将是最长的回文序列。
该解决方案也是 O(n^2) 解决方案。
子串和子序列的区别让我有点困惑。（见Ex6.8和6.11） 根据我们对子序列的理解，给出的例子没有回文子序列ACGCA。这是我的伪代码，我不太确定初始化><
for i = 1 to n do
for j = 1 to i-1 do
L(i,j) = 0
for i = 1 to n do
L(i,i) = 1
for i = n-1 to 1 do //pay attention to the order when filling the table
for j = i+1 to n do
if x[i] = x[j] then
L(i,j) = 2 + L(i+1, j-1)
else do
L(i,j) = max{L(i+1, j), L(i, j-1)}
return max L(i,j)
为算法决赛做准备...
最长回文序列的工作 Java 实现
public class LongestPalindrome
{
int max(int x , int y)
{
return (x>y)? x:y;
}
int lps(char[] a ,int i , int j)
{
if(i==j) //If only 1 letter
{
return 1;
}
if(a[i] == a[j] && (i+1) == j) // if there are 2 character and both are equal
{
return 2;
}
if(a[i] == a[j]) // If first and last char are equal
{
return lps(a , i+1 , j-1) +2;
}
return max(lps(a,i+1 ,j),lps(a,i,j-1));
}
public static void main(String[] args)
{
String s = "NAMAN IS NAMAN";
LongestPalindrome p = new LongestPalindrome();
char[] c = s.toCharArray();
System.out.print("Length of longest seq is" + p.lps(c,0,c.length-1));
}
}
导入 java.util.HashSet；
导入 java.util.Scanner；
/** * @param args * 给定一个字符串，我们需要在该字符串中找到最长的回文子序列 * 在这段代码中，我们使用 hashset 来确定给定字符串中子字符串的唯一集合 */
公共类 NumberOfPalindrome {
/**
* @param args
* Given a string find the longest possible substring which is a palindrome.
*/
public static HashSet<String> h = new HashSet<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
for(int i=0;i<=s.length()/2;i++)
h.add(s.charAt(i)+"");
longestPalindrome(s.substring(0, (s.length()/2)+(s.length()%2)));
System.out.println(h.size()+s.length()/2);
System.out.print(h);
}
public static void longestPalindrome(String s){
//System.out.println(s);
if(s.length()==0 || s.length()==1)
return;
if(checkPalindrome(s)){
h.add(s);
}
longestPalindrome(s.substring(0, s.length()-1));
longestPalindrome(s.substring(1, s.length()));
}
public static boolean checkPalindrome(String s){
//System.out.println(s);
int i=0;int j=s.length()-1;
while(i<=j){
if(s.charAt(i)!=s.charAt(j))
return false;
i++;j--;
}
return true;
}
}
private static int findLongestPalindromicSubsequence(String string) {
int stringLength = string.length();
int[][] l = new int[stringLength][stringLength];
for(int length = 1; length<= stringLength; length++){
for(int left = 0;left<= stringLength - length;left++){
int right = left+ length -1;
if(length == 1){
l[left][right] = 1;
}
else{
if(string.charAt(left) == string.charAt(right)){
//L(0, n-1) = L(1, n-2) + 2
if(length == 2){
// aa
l[left][right] = 2;
}
else{
l[left][right] = l[left+1][right-1]+2;
}
}
else{
//L(0, n-1) = MAX ( L(1, n-1) , L(0, n-2) )
l[left][right] = (l[left+1][right] > l[left][right-1])?l[left+1][right] : l[left][right-1];
}
}
}
}
return l[0][stringLength-1];
}
从给定字符串中查找最长回文子串的程序。
package source;
import java.util.ArrayList;
public class LongestPalindrome
{
//Check the given string is palindrome by
public static boolean isPalindrome (String s)
{
StringBuffer sb = new StringBuffer(s);
if(s.equalsIgnoreCase(sb.reverse().toString()))
return true;
else
return false;
}
public static void main(String[] args)
{
//String / word without space
String str = "MOMABCMOMOM"; // "mom" //"abccbabcd"
if(str.length() > 2 )
{
StringBuffer sb = new StringBuffer();
ArrayList<String> allPalindromeList = new ArrayList<>();
for(int i=0; i<str.length(); i++)
{
for(int j=i; j<str.length(); j++)
{
sb.append(str.charAt(j));
if( isPalindrome(sb.toString()) ) {
allPalindromeList.add(sb.toString());
}
}
//clear the stringBuffer
sb.delete(0, sb.length());
}
int maxSubStrLength = -1;
int indexMaxSubStr = -1;
int index = -1;
for (String subStr : allPalindromeList) {
++index;
if(maxSubStrLength < subStr.length()) {
maxSubStrLength = subStr.length();
indexMaxSubStr = index;
}
}
if(maxSubStrLength > 2)
System.out.println("Maximum Length Palindrome SubString is : "+allPalindromeList.get(indexMaxSubStr));
else
System.out.println("Not able to find a Palindrome who is three character in length!!");
}
}
}
对于字符串中的每个字母：
将字母设置为回文的中间（当前长度 = 1）
检查如果这是它的中间，回文将是多长时间
如果这个回文比我们找到的长（直到现在）：保留回文的索引和大小。
O(N^2) ：因为我们有一个选择中间的循环和一个检查回文长度的循环，如果这是中间的话。每个循环从 0 运行到 O(N) [第一个从 0 到 N-1，第二个从 0 到 (N-1)/2]
例如：DBABCBA
i=0 : D 是回文的中间，不能长于 1（因为它是第一个）
i=1：B 是回文的中间，检查 B 前后的字符：不相同（一侧为 D，另一侧为 A）--> 长度为 1。
i=2 ：A 是回文的中间，检查 A 前后的字符：B --> 长度均为 3。检查间隙为 2 的字符：不相同（一侧为 D，另一侧为 C）-->长度为 3。
等等
输入： A1,A2,....,An
目标： 找到最长的严格递增的子序列（不一定是连续的）。
L(j)：以 j 结尾的最长严格递增子序列
L(j): max{ L(i)}+1 } where i < j and A[i] < A[j]
然后找到max{ L(j) } for all j
您将在此处获得源代码