题解 | #密码截取#

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findMax(string temp, char a)
{
    if (temp.size() == 1)
        return 2;
    for (int i = 0; i != temp.size(); ++i)
    {
        if (temp[i] == a)
        {
            if (i == temp.size() - 1)
                return 2;
            int k = temp.size() - i - 1;
            if ( k % 2 == 0)
            {
                string re = temp.substr(i + 1 + k / 2, k / 2);
                reverse(re.begin(), re.end());
                if (temp.substr(i + 1, k/2) == re)
                    return k+2;
            }
            else
            {

                string re = temp.substr(i + 1 + (k + 1) / 2, (k - 1) / 2);
                reverse(re.begin(), re.end());
                if (temp.substr(i + 1, (k - 1) / 2) == re)
                    return k + 2;
            }
        }
    }
    return 0;
}

int main() {
    string str;
    getline(cin,str);
    string temp;
    vector<int> result(str.size()+1,0);
    result[1] = 1;
    temp.push_back(str[0]);
    for(int i = 1;i!=str.size();++i)
    {
        result[i+1] = max(result[i],findMax(temp,str[i]));
        temp.push_back(str[i]);
    }
    cout<<result[temp.size()];
}
// 64 位输出请用 printf("%lld")

动态规划思路，加入第i个字符，两种可能，此时字符串最大值不需要第i个字符，如果要用第i个字符，那么一定需要找到里面头尾是第i个字符的最大回文数。