Longest Palindromic Subsequence

Given a string S, determine the length of the longest palindromic subsequence that can be formed from S. A palindromic subsequence is a sequence that reads the same backward as forward and does not require contiguous characters from the original string.

You can solve this problem using dynamic programming. The recurrence relation used is:

$$ \text{dp}[i][j] = \begin{cases} 1 & \text{if } i = j,\\[6pt] 2 & \text{if } S[i] = S[j] \text{ and } j = i+1,\\[6pt] 2 + \text{dp}[i+1][j-1] & \text{if } S[i] = S[j] \text{ and } j > i+1,\\[6pt] \max(\text{dp}[i+1][j],\;\text{dp}[i][j-1]) & \text{if } S[i] \neq S[j]. \end{cases} $$

Your task is to read the input string from standard input and output the length of its longest palindromic subsequence to standard output.

inputFormat

The input consists of a single line containing the string S composed of uppercase English letters. The length of S can be up to 1000 characters.

outputFormat

Output a single integer representing the length of the longest palindromic subsequence of the input string.

ABBDCACB

5