题解 | #密码截取#

//动态规划，但感觉占用空间比较多（但是上三角矩阵记得可以一维数组存储来着），看的b站思路。
#include <stdio.h>
#include <string.h>
int main() {
    char str[2501]={0};
    scanf("%s",str);
    int len=strlen(str);
    short arr[len][len];
    memset(arr,0,sizeof(arr));
    int i=0;
    int j=0;
    for(i=0;i<len;i++)
    arr[i][i]=1;
    for(j=1;j<len;j++)
    {
        for(i=0;i<j;i++)
        {
            if(str[i]!=str[j])
            arr[i][j]=0;
            else
            {
                if(j-i<3)
                arr[i][j]=1;
                else
                arr[i][j]=arr[i+1][j-1];
            }
        }
    }
    int max=0;
    for(i=0;i<len;i++)
    {
        for(j=0;j<len;j++)
        {
            if(arr[i][j]&&max<(j-i+1))
            {
                max=j-i+1;
            }
        }
    }
    printf("%d",max);
    return 0;
}