blocks|key|167346|text|你的算法返回的是一个花球的最大长度，而不是两个长度的乘积的最大值。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|167347|更新|167348|这里有一个可能的解决方案：|167349|public+static+int+max(String+s)+{
++++int+max+=+0;
++++for+(int+i+=+1;+i+<+s.length()-1;+%2B%2Bi)+{
++++++++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+%2B+"+"+%2B+p2+%2B+"+->+"+%2B+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)+%2B+bestPalyndrome(s,+start%2B1,+end-1)
++++++++++++++++%2B+s.charAt(end-1);
++++}+else+{
++++++++String+s1+=+bestPalyndrome(s,+start,+end-1);
++++++++String+s2+=+bestPalyndrome(s,+start%2B1,+end);
++++++++return+s2.length()+>+s1.length()+?+s2+:+s1;
++++}
}|code-block|syntax|javascript|167350|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|O|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|P|8|@]|9|@]|A|$I|J]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Your algorithm returns the maximum length of a palyndrome, not the maximum of the product of two lengths.

UPDATE

Here's a possible solution:

<pre><code>public static int max(String s) {
 int max = 0;
 for (int i = 1; i &lt; 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 &gt; max) {
 System.out.println(p1 + " " + p2 + " -&gt; " + prod);
 max = prod;
 }
 }
 return max;
}

private static String bestPalyndrome(String s, int start, int end) {
 if (start &gt;= 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() &gt; s1.length() ? s2 : s1;
 }
}
</code></pre>

blocks|key|2913679|text|首先，你应该使用自下而上的方法遍历dp表，找出最长的回文子序列的长度，然后你可以通过将dpi与dpj%2B1相乘来计算最大乘积:下面是C%2B%2B中的代码；|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2913680|int+longestPalindromicSubsequenceProduct(string+x){
int+n+=+x.size();
vector<vector<int>>+dp(n,vector<int>(n,0));
for(int+i=0;i<n;i%2B%2B){
++++dp[i][i]+=+1;
}
for(int+k=1;k<n;k%2B%2B){
for(int+i=0;i<n-k;i%2B%2B){
++++++++int+j+=+i+%2B+k;
++++++++++++if(x[i]==x[j]){
++++++++++++++++dp[i][j]+=+2+%2B+dp[i%2B1][j-1];
++++++++++++}+else{
++++++++++++++++dp[i][j]+=+max(dp[i][j-1],dp[i%2B1][j]);
++++++++++++}
+++}
}
int+maxProd+=+0;
for(int+i=0;i<n;i%2B%2B){
++++for(int+j=0;j<n-1;j%2B%2B){
++++++++maxProd+=+max(maxProd,dp[i][j]*dp[j%2B1][n-1]);
++++++}
+++}
return+maxProd;
}|code-block|syntax|javascript|2913681|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Firstly you should traverse the dp table to find out the length of longest palindromic subsequences using bottom up approach, then you can calculate the max product by multiplying dp[i][j] with dp[j+1][n-1] : Given below is the code in C++;

<pre><code>int longestPalindromicSubsequenceProduct(string x){
int n = x.size();
vector&lt;vector&lt;int&gt;&gt; dp(n,vector&lt;int&gt;(n,0));
for(int i=0;i&lt;n;i++){
 dp[i][i] = 1;
}
for(int k=1;k&lt;n;k++){
for(int i=0;i&lt;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&lt;n;i++){
 for(int j=0;j&lt;n-1;j++){
 maxProd = max(maxProd,dp[i][j]*dp[j+1][n-1]);
 }
 }
return maxProd;
}
</code></pre>

blocks|key|2073503|text|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%2B%2B)+dp[i][i]=1;

+for+(int+cl=2;+cl<=n;+cl%2B%2B)+{
++++for+(int+i=0;+i<n-cl%2B1;+i%2B%2B){
++++++++int+j+=+i%2Bcl-1;+
++++++++if+(s[i]+==+s[j]+&&+cl+==+2)+dp[i][j]+=+2;+
++++++++else+if+(s[i]+==+s[j])+dp[i][j]+=+dp[i%2B1][j-1]+%2B+2;+
++++++++else+dp[i][j]+=+max(dp[i][j-1],+dp[i%2B1][j]);+
++++}+
}
for(int+i=0;i<n-1;i%2B%2B){
+++m+=+max(+m,+dp[0][i]*dp[i%2B1][n-1]+);
}+
return+m;|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|2073504|}|unstyled|2073505|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|J|8|@]|9|@]|A|$]]|$1|G|3|-4|5|F|7|K|8|@]|9|@]|A|$]]]|H|$]]

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

 for (int cl=2; cl&lt;=n; cl++) {
 for (int i=0; i&lt;n-cl+1; i++){
 int j = i+cl-1; 
 if (s[i] == s[j] &amp;&amp; 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&lt;n-1;i++){
 m = max( m, dp[0][i]*dp[i+1][n-1] );
} 
return m;
</code></pre>
}

blocks|key|2913701|text|++++int+palSize(string+&s,+int+mask)+{
++++int+p1+=+0,+p2+=+s.size(),+res+=+0;
++++while+(p1+<=+p2)+{
++++++++if+((mask+&+(1+<<+p1))+==+0)
++++++++++++%2B%2Bp1;
++++++++else+if+((mask+&+(1+<<+p2))+==+0)
++++++++++++--p2;
++++++++else+if+(s[p1]+!=+s[p2])
++++++++++++return+0;
++++++++else
++++++++++++res+%2B=+1+%2B+(p1%2B%2B+!=+p2--);
++++}
++++return+res;
}
int+maxProduct(string+s)+{
++++int+mask[4096]+=+{},+res+=+0;
++++for+(int+m+=+1;+m+<+(1+<<+s.size());+%2B%2Bm)
++++++++mask[m]+=+palSize(s,+m);
++++for+(int+m1+=+1;+m1+<+(1+<<+s.size());+%2B%2Bm1)
++++++++if+(mask[m1])
++++++++++++for+(int+m2+=+1;+m2+<+(1+<<+s.size());+%2B%2Bm2)
++++++++++++++++if+((m1+&+m2)+==+0)
++++++++++++++++++++res+=+max(res,+mask[m1]+*+mask[m2]);
++++return+res;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|2913702|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code> int palSize(string &amp;s, int mask) {
 int p1 = 0, p2 = s.size(), res = 0;
 while (p1 &lt;= p2) {
 if ((mask &amp; (1 &lt;&lt; p1)) == 0)
 ++p1;
 else if ((mask &amp; (1 &lt;&lt; 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 &lt; (1 &lt;&lt; s.size()); ++m)
 mask[m] = palSize(s, m);
 for (int m1 = 1; m1 &lt; (1 &lt;&lt; s.size()); ++m1)
 if (mask[m1])
 for (int m2 = 1; m2 &lt; (1 &lt;&lt; s.size()); ++m2)
 if ((m1 &amp; m2) == 0)
 res = max(res, mask[m1] * mask[m2]);
 return res;
}
</code></pre>

blocks|key|2073520|text|您可以遍历所有不重叠的回文子序列并返回最大值。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2073521|++public+int+longestPalindromicSubsequenceProduct(String+str)+{
++++int+maxProduct+=+0;
++++for+(int+k+=+0;+k+<+str.length();+k%2B%2B)+{
++++++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+%2B+1][cols+%2B+1];

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

++++return+dp[rows][cols];
++}|code-block|syntax|javascript|2073522|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

You can loop through all non-overlapping palindromic subsequences and return the maximum value.
<pre class="lang-java prettyprint-override"><code>
 public int longestPalindromicSubsequenceProduct(String str) {
 int maxProduct = 0;
 for (int k = 0; k &lt; 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 &lt;= rows; r++) {
 for (int c = 1; c &lt;= 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];
 }


</code></pre>

I am trying to find the maximum product of two non overlapping palindromic sub-sequences of string <code>s</code> that we'll refer to as <code>a</code> and <code>b</code>. I came up with below code but it's not giving correct output:

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

 for (int i = s.length() - 1; i &gt;= 0; i--) {
 dp[i][i] = 1;
 for (int j = i+1; j &lt; 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];
}
</code></pre>

For input string "acdapmpomp", we can choose <code>a</code> = "aca" and <code>b</code> ="pmpmp" to get a maximal product of score 3 * 5 = 15. But my program gives output as 5.

Find the maximum product of two non overlapping palindromic subsequences

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我正在尝试寻找字符串s的两个不重叠的回文子序列的最大乘积，我们将其称为a和b。我想出了以下代码，但它没有给出正确的输出：public static int max(String s) {    int[][] dp = new int[s.length()][s.length()];    for (int i = s...

问求两个不重叠的回文子序列的最大乘积
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问求两个不重叠的回文子序列的最大乘积EN