All possible middle elements, for largest odd length palindrome subsquence of a string

0
votes

How to find all possible middle elements for the longest palindrome subsequence of a string . Considering that the length of longest palindrome subsequence is odd .

1
algorithmdynamic-programming
can you share what you have tried so far ? - marvel308

1 Answers

0
votes

You can use the logic for Longest Palindromic Subsequence and extend it for your case.

Let DP(i,j,k) denote the maximum answer with j as the middle element and current index is i and k. Now 

if(i==j && j==k)
    return 1;
if(S[i] == S[j])
    DP(i,j,k) = 1 + DP(i+1, j, k-1)
DP(i,j,k) = max(DP(i,j,k), max(DP(i+1,j,k), DP(i,j,k-1)))

calculate it for all possible values of i,j,k , the maximum value would be your answer. Time Complexity O(n^3)