Find the maximum product of two non overlapping palindromic subsequences

Question

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

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];
}

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

Answer 1

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

Answer 2

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++;

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