package string

func LongestPalindromeSeq(s string) int {
	n := len(s)
	var ret = 1

	for i := 0; i < n; i++ {
		for l, r := i-1, i+1; l >= 0 && r < n && s[l] == s[r]; l, r = l-1, r+1 {
			ret = max(r-l+1, ret)
		}

		for l, r := i, i+1; l >= 0 && r < n && s[l] == s[r]; l, r = l-1, r+1 {
			ret = max(r-l+1, ret)
		}
	}

	return ret
}

func LongestPalindromeSubSeq(s string) int {
	n := len(s)
	if n < 2 {
		return n
	}

	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
		dp[i][i] = 1
	}

	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if s[i] == s[j] {
				dp[i][j] = dp[i+1][j-1] + 2
			} else {
				dp[i][j] = max(dp[i+1][j], dp[i][j-1])
			}
		}
	}

	return dp[0][n-1]
}

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