题解 | #最长回文子串#

解法：

动态规划, 状态转移矩阵Matrix[n][n], 以left代表子串开头位置,right代表子串结尾位置, left <= right  
如果子串不是回文字符串, Matrix[left][right] = 0，,
如果子串是回文字符串, Matrix[left][right] = right - left + 1;

如果Matrix[left+1][right-1] > 0，判断A[left和A[right]是否相等，如果相等，那么Matrix[left][right]肯定也是回文子串，否则Matrix[left][right]一定不是回文子串。

如果A[left]==A[right]，字符串从left到right能不能构成回文子串还需要进一步判断:
    如果left==right，也就是说只有一个字符，我们认为他是回文子串。即Matrix[left][right] = 1
    如果right-left <= 2，类似于"aa"，或者"aba"，我们认为他是回文子串。即Matrix[left][right] = right - left + 1
    如果right-left > 2，需要判断Matrix[left+1][right-1] > 0，若大于0, 则Matrix[left][right] = Matrix[left+1][right-1] + 2, 否则Matrix[left][right] = 0;

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        int matrix[n][n];
//         for(int i = 0; i < n; i++)
//         {
//             for(int j = 0; j < n; j++)
//                 matrix[i][j] = 0;
//         }
        int left = 0;
        int right = 0;
        int maxLen = 0;
        for(; right < n; right++)
        {
            for(left = 0; left <= right; left ++)
            {
                if(A[left] != A[right])
                {
                    matrix[left][right] = 0;
                    continue;
                }

                if(left ==  right)
                {
                    matrix[left][right] = 1;
                }
                else if((right - left)  <= 2)
                {
                    matrix[left][right] = right - left + 1;
                }
                else
                {
                    if (left + 1 > right - 1)
                        matrix[left][right] = 2;
                    else if (matrix[left+1][right-1] > 0)
                        matrix[left][right] = matrix[left+1][right-1] + 2;
                    else
                        matrix[left][right] = 0;
                }
                if (matrix[left][right] > maxLen)
                    maxLen = matrix[left][right];
            }
        }
//         for(int i = 0; i < n; i++)
//         {
//             for(int j = 0; j < n; j++)
//                 cout<<matrix[i][j]<<" ";
//             cout<<endl;
//         }
        return maxLen;
    }
};