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

algorithm data-structures java

2022-09-04 22:40:38

我试图找到字符串的两个非重叠回文子序列的最大乘积，我们将它们称为和。我想出了下面的代码，但它没有给出正确的输出：sab

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”，我们可以选择= “aca”和=“pmpmp”来获得得分3 * 5 = 15的最大乘积。但是我的程序给出的输出为5。ab

答案 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;
}

答案 2

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;

}