package question;

public class Question516 {
 public static void main(String[] args) {
 String s = "abaabaa";
 new Question516().longestPalindromeSubseq(s);
 }

 public int longestPalindromeSubseq(String s) {
 int[][] dp = new int[s.length()][s.length()];
 for (int i = 0; i < s.length(); i++) dp[i][i] = 1;
 for (int k = 1; k < s.length(); k++) {
 for (int i = 0; i + k < s.length(); i++) {
 int j = i + k;
 if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
 else dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
 }
 }
 return dp[0][s.length() - 1];
 }
}