其他 最长回文子串 动态规划

题目描述

对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。

给定字符串A以及它的长度n，请返回最长回文子串的长度。

测试样例：

"abc1234321ab",12
返回：7

class Palindrome {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        // 字符串A及长度n
        bool dp[n][n];
        for(int i=0;i<n;++i)
        {
            dp[i][i]=true;
        }    
        for(int i=0;i<n-1;++i)
        {
            dp[i][i+1]=(A[i]==A[i+1])?true:false;
        }
        for(int len = 3;len<=n;++len)
        {
            for(int i=0;i<=n-len;++i)
            {
                int j=i+len-1;
                if(A[i]==A[j])
                {
                    dp[i][j]=dp[i+1][j-1];
                }else 
                {
                    dp[i][j]=false;
                }
            }
        }
        int ans=-1;
        for(int len=1;len<=n;++len)
        {
            for(int i=0;i<=n-len;++i)
            {
                int j = i+len-1;
                if(dp[i][j])
                {
                    ans=max(ans,len);
                }
            }
        }
        return ans;
    }
};