题解 | #最长回文子串#

package main

import (
    "fmt"
)

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func longestPariomSubstring(s string) int {
    var maxLenght int
    size := len(s)

    // dp[i][j]: 表示 s[i,j]是否是回文字串
    dp := make([][]bool, size)
    for i:=0; i<len(dp); i++ {
        dp[i] = make([]bool, size)
    }

    // 初始化
    
    // 动态转移方程
    for i:=size-1; i>=0; i-- {
        for j:=i; j<size; j++ {
            if s[i] == s[j] && (j-i<=2 || dp[i+1][j-1]) {
                dp[i][j] = true
                maxLenght = max(maxLenght, j-i+1)
            }
        }
    }

    return maxLenght
}

func main() {
    var s string
    fmt.Scan(&s)
    fmt.Println(longestPariomSubstring(s))
}

// 本题输入为一个字符串，所以采用：fmt.Scan(&s)