题解 | #最长回文子串#

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        if (n <= 1)
            return n;
        int maxLen = 0; // 记录子串最长值
        vector<vector<bool>> dp(A.size(), vector<bool>(A.size())); // dp[left][right] true表示从left到right构成回文子串
                                                                  // (闭区间)
        for (int right = 1; right < A.size(); right++) {
            for (int left = 0; left < right; left++) {
                if (A[left] != A[right]) // 回文串不可能存在
                    continue;
                if (right - left <= 2) // aba or aa
                    dp[left][right] = true;
                else if (dp[left + 1][right - 1]) // 若[left + 1][right - 1]间构成回文串，则回文串长度增长
                    dp[left][right] = true;
                else
                    dp[left][right] = false;
                if (dp[left][right] && right - left + 1 > maxLen)
                    maxLen = right - left + 1;
            }
        }

        return maxLen;
    }
};