Найти максимальное произведение двух непересекающихся палиндромных подпоследовательностей

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.

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

Answer 2

Ваш алгоритм возвращает максимальную длину палиндрома, а не максимум произведения двух длин.

ОБНОВЛЕНИЕ

Вот возможное решение:

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