求两个不重叠的回文子序列的最大乘积
求两个不重叠的回文子序列的最大乘积
提问于 2018-12-07 13:24:36
我正在尝试寻找字符串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。
回答 5
Stack Overflow用户
发布于 2019-07-26 10:36:05
首先，你应该使用自下而上的方法遍历dp表，找出最长的回文子序列的长度，然后你可以通过将dpi与dpj+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;
}Stack Overflow用户
发布于 2020-11-07 20:01:00
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;}
Stack Overflow用户
发布于 2021-09-12 04:10:54
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;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53663721
复制相关文章
相似问题
腾讯云开发者
