寻找两个非重叠回文子序列的最大乘积

Question

我正在尝试找到字符串s的两个非重叠回文子序列a和b的最大乘积。我编写了下面的代码，但它没有给出正确的输出:

public static int max(String s) {
    int[][] dp = new int[s.length()][s.length()];

    for (int i = s.length() - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i+1; j < s.length(); j++) {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][s.length()-1];
}

对于输入字符串 "acdapmpomp"，我们可以选择 a = "aca" 和 b = "pmpmp" 来获得分数为 3 * 5 = 15 的最大乘积。但是我的程序输出为 5。

- flash

---

@nbrooks 他们确实是非重叠回文字符串，但并不完全是子字符串。 - Naman

@flash 首先，for (int i = s.length() - 1; i >= 0; i--) { dp[i][i] = 1; 这个初始化不应该与处理循环分开吗？ - Naman

上面的链接也会产生与我的程序一样的输出，都是5。 - flash

@TharakaRatnayake 看起来这个问题已经被删除了。 - Maurice Perry

A) 我认为您的要求不够清晰。例如，当输入字符串包含0、1或3个回文时，应该发生什么？ B) 您的第一个目标应该是获得正确的结果。也就是说：编写最简单的代码。比如：首先编写提取回文字符串的代码。为什么？因为这样您可以首先专注于问题的这一部分（哪些是有效的回文）。您可以为此编写单元测试，而不是查看难以解释的整数计数器，而是查看字符串和子字符串。然后，当那部分工作正常时... - GhostCat

然后，当您拥有能够提供正确结果的工作代码（并且已经有足够多的测试用例验证该代码）时...那么您可以继续进行所需的计算。最后，如果您发现性能不足，那么就进入重构解决方案。这才是真正的关键：不要一次性解决所有问题，而是将问题分解为可能的最小部分。解决这些问题，然后从这些较小的部分构建整体解决方案。 - GhostCat

Answer 1

首先，您应该使用自底向上的方法遍历dp表，以找出最长回文子序列的长度，然后可以通过将dp [i] [j]乘以dp [j + 1] [n-1]来计算最大乘积：以下是C ++中的代码；

int longestPalindromicSubsequenceProduct(string x){
int n = x.size();
vector<vector<int>> dp(n,vector<int>(n,0));
for(int i=0;i<n;i++){
    dp[i][i] = 1;
}
for(int k=1;k<n;k++){
for(int i=0;i<n-k;i++){
        int j = i + k;
            if(x[i]==x[j]){
                dp[i][j] = 2 + dp[i+1][j-1];
            } else{
                dp[i][j] = max(dp[i][j-1],dp[i+1][j]);
            }
   }
}
int maxProd = 0;
for(int i=0;i<n;i++){
    for(int j=0;j<n-1;j++){
        maxProd = max(maxProd,dp[i][j]*dp[j+1][n-1]);
      }
   }
return maxProd;
}

- Shubham Patel

---

我认为这种方法不正确。在“bacbac”上尝试一下。答案应该是9（对于子字符串“bab”和“cac”）。你的代码输出3。 - rupinderg00

问题说“非重叠回文子序列”。bab和cac是重叠的。希望这可以帮到你。 - Shubham Patel

@rupinderg00，这种方法是不正确的，请尝试在"aebgcbea"上进行测试。{"abcba"，"ege"}答案为15，而这段代码将打印5，因为你认为每个回文子串都在其中一半。 - Sumit Joshi

@SumitJoshi abcba和ege重叠了..我们正在寻找不重叠的部分 :) - Shubham Patel

Answer 2

    int palSize(string &s, int mask) {
    int p1 = 0, p2 = s.size(), res = 0;
    while (p1 <= p2) {
        if ((mask & (1 << p1)) == 0)
            ++p1;
        else if ((mask & (1 << p2)) == 0)
            --p2;
        else if (s[p1] != s[p2])
            return 0;
        else
            res += 1 + (p1++ != p2--);
    }
    return res;
}
int maxProduct(string s) {
    int mask[4096] = {}, res = 0;
    for (int m = 1; m < (1 << s.size()); ++m)
        mask[m] = palSize(s, m);
    for (int m1 = 1; m1 < (1 << s.size()); ++m1)
        if (mask[m1])
            for (int m2 = 1; m2 < (1 << s.size()); ++m2)
                if ((m1 & m2) == 0)
                    res = max(res, mask[m1] * mask[m2]);
    return res;
}

- Shubham Kumar Gupta

Answer 3

int multiplyPalindrome(string s) {
int n=s.size(),m=0;
vector<vector<int>> dp(n, vector<int> (n));
for(int i=0;i<n;i++) dp[i][i]=1;

 for (int cl=2; cl<=n; cl++) {
    for (int i=0; i<n-cl+1; i++){
        int j = i+cl-1; 
        if (s[i] == s[j] && cl == 2) dp[i][j] = 2; 
        else if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2; 
        else dp[i][j] = max(dp[i][j-1], dp[i+1][j]); 
    } 
}
for(int i=0;i<n-1;i++){
   m = max( m, dp[0][i]*dp[i+1][n-1] );
} 
return m;

}

- MOHIT BHATIA

---

我认为这种方法不正确。在“bacbac”上尝试一下。答案应该是9（对于子字符串“bab”和“cac”）。你的代码打印出3。 - rupinderg00

Answer 4

你可以循环遍历所有非重叠回文子序列并返回最大值。

  public int longestPalindromicSubsequenceProduct(String str) {
    int maxProduct = 0;
    for (int k = 0; k < str.length(); k++) {
      String left = str.substring(0, k);
      String right = str.substring(k);
      int currProduct = longestPalindromicSubsequence(left) * longestPalindromicSubsequence(right);
      maxProduct = Math.max(maxProduct, currProduct);
    }

    return maxProduct;
  }

  private int longestPalindromicSubsequence(String org) {
    String rev = new StringBuilder(org).reverse().toString();
    return longestCommonSubsequence(org, rev);
  }

  private int longestCommonSubsequence(String str1, String str2) {
    int rows = str1.length();
    int cols = str2.length();

    int[][] dp = new int[rows + 1][cols + 1];

    for (int r = 1; r <= rows; r++) {
      for (int c = 1; c <= cols; c++) {
        if (str1.charAt(r - 1) == str2.charAt(c - 1)) dp[r][c] = 1 + dp[r - 1][c - 1];
        else dp[r][c] = Math.max(dp[r - 1][c], dp[r][c - 1]);
      }
    }

    return dp[rows][cols];
  }

- Arjun Sunil Kumar

Answer 5

你的算法返回最长回文串的长度，而不是两个长度乘积的最大值。

更新：

以下是可能的解决方案：

public static int max(String s) {
    int max = 0;
    for (int i = 1; i < s.length()-1; ++i) {
        String p1 = bestPalyndrome(s, 0, i);
        String p2 = bestPalyndrome(s, i, s.length());
        int prod = p1.length()*p2.length();
        if (prod > max) {
            System.out.println(p1 + " " + p2 + " -> " + prod);
            max = prod;
        }
    }
    return max;
}

private static String bestPalyndrome(String s, int start, int end) {
    if (start >= end) {
        return "";
    } else if (end-start == 1) {
        return s.substring(start, end);
    } else  if (s.charAt(start) == s.charAt(end-1)) {
        return s.charAt(start) + bestPalyndrome(s, start+1, end-1)
                + s.charAt(end-1);
    } else {
        String s1 = bestPalyndrome(s, start, end-1);
        String s2 = bestPalyndrome(s, start+1, end);
        return s2.length() > s1.length() ? s2 : s1;
    }
}

- Maurice Perry