Longest Palindromic Substring

最长回文子串

动态规划的方法的参考Palindrome Partitioning （回文子串题）

代码：

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        int dp[1000][1000];
        memset(dp,0,sizeof(dp));
        for (int i = n-1; i >=0; --i)
        {
            for (int j = i; j < n; ++j)
            {
                if(j==i){
                    dp[i][j]=1;
                }else if(j==i+1){
                    if(s[i]==s[j]) dp[i][j]=1;
                }
                else{
                    if(s[i]==s[j]&&dp[i+1][j-1]) dp[i][j]=1;
                }
            }
        }
        //在数组中找出长度最大的子串
        int max=0;
        int maxi=-1;int maxj=-1;
        for(int i=0;i<n;++i){
            for(int j=i;j<n;++j){
                if(dp[i][j]&&j-i+1>max) {
                    max=j-i+1;maxi=i;maxj=j;
                }
            }
        }
        return s.substr(maxi,maxj-maxi+1);
    }
};