题解 | #最长回文子串#

using System;
using System.Linq;

namespace HJ85
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string strInput = Console.ReadLine();
            //int max = GetMaxCount01(strInput);
            int max = GetMaxCount02(strInput);
            Console.WriteLine(max);
        }


        /// <summary>中心扩散法求最长回文中串长度 </summary>
        private static int GetMaxCount01(string s)
        {
            char[] charArray = s.ToCharArray();

            int max = 0;
            //左移指针
            int left;
            //右移指针
            int right;

            for (int i = 1; i < charArray.Length; i++)
            {

                left = i - 1;
                right = i + 1;
                //ABA型，以i为中心为中心向两边扩散
                while (true)
                {
                    if (left >= 0 && right < charArray.Length && charArray[left] == charArray[right])
                    {
                        if (right - left + 1 > max)
                        {
                            max = right - left + 1;
                        }
                    }
                    else
                    {
                        break;
                    }
                    left--;
                    right++;
                }


                left = i;
                right = i + 1;
                //ABBA型，以（i，i+1）为中心向两边扩散
                while (true)
                {
                    if (left >= 0 && right < charArray.Length && charArray[left] == charArray[right])
                    {
                        if (right - left + 1 > max)
                        {
                            max = right - left + 1;
                        }
                    }
                    else
                    {
                        break;
                    }
                    left--;
                    right++;
                }
            }
            return max;
        }

        /// <summary>
        /// 动态规划法
        /// </summary>
        private static int GetMaxCount02(string s)
        {
            char[] charArray = s.ToCharArray();

            int length = charArray.Length;

            int max = 0;

            //dp[i,j]代表[j...i]能否形成回文串
            bool[,] dp = new bool[length, length];

            for (int i = 0; i < charArray.Length; i++)
            {
                for (int j = 0; j <= i; j++)
                {
                   
                    if (i - j == 0) //ABA型初始状态
                    {
                        dp[i, j] = true;
                    }
                    else if (i - j == 1 && charArray[i] == charArray[j])//ABBA型初始状态
                    {
                        dp[i, j] = true;
                    }
                    //除了i-j==0,i-j==1,就是i-j>1的状态了，此时会在前面两个初始状态下进行转移
                    //i-j==偶数，是在i-j==0（ABA型）的基础上转移，
                    //i-j==奇数，是在i-j==1（ABBA型）的基础上转移，
                    else
                    {  
                       // dp[i, j] 上一次对此次状态有决策意义的是dp[i - 1, j + 1]，其它状态不用管
                       //如果[j+1...i-1]是回文串，并且此时charArray[i] == charArray[j]，[j,j+1...i-1,i]也是回文串
                       //而dp[i - 1, j + 1]==true，可能i-1=j+1，也有可能dp[i - 2， j + 2]=true以此类推
                        if (dp[i - 1, j + 1] && charArray[i] == charArray[j])
                        {
                            dp[i, j] = true;
                        }
                    }

                    //更新最大长度
                    if (dp[i, j] && i - j + 1 > max)
                    {
                        max = i - j + 1;
                    }
                }
            }


            return max;
        }
    }
}