题解 | #最长回文子串#

'''
解题思路：
动态规划算法，
dp[i][j]定义为：如果dp[i][j]为1，则表示字符串从i到j是回文子串，
               如果dp[i][j]为0，则表示字符串从i到j不是回文子串。
1、当i==j时，dp[i][j]==1
2、当j-i<=2时，如s[i]==s[j]，dp[i][j]==1
3、其它情况，如s[i]==s[j]，当dp[i+1][j-1]==1，则dp[i][j]==1
由于递推公式：
dp[i][j] = dp[i+1][j-1]==1，条件是s[i]==s[j]，i要从大的数值，j要从小的数值开始计算
#=============================================================================================
'''
# -*- coding:utf-8 -*-

class Solution:
    def getLongestPalindrome(self, A, n):
        # write code here
        #print(A)
        #print(n)
        dp = [[0]*n for _ in range(n)]
        maxlen = 1
        str1 = ''
        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if A[i]==A[j]:                    
                    if j-i<=2:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i+1][j-1]

                if dp[i][j]==1 and j-i+1>maxlen:
                    maxlen = j-i+1
        #            str1 = A[i:j+1]
        #for i in dp:
        #    print(i)
        #print(str1)
        return maxlen

A = 'abc1234321ab'   # 7
n = len(A)
s = Solution()
print(s.getLongestPalindrome(A,n))