Longest Palindromic Subsequence

1public int longestPalindromeSubseq(String s) {
2    int n = s.length();
3    int[][] dp = new int[n][n];
4
5    // Single character palindromes
6    for (int i = 0; i < n; i++) {
7        dp[i][i] = 1;
8    }
9
10    // Check palindromes of increasing lengths
11    for (int len = 2; len <= n; len++) {
12        for (int i = 0; i <= n - len; i++) {
13            int j = i + len - 1;
14
15            // If characters at start and end are the same
16            if (s.charAt(i) == s.charAt(j)) {
17                dp[i][j] = 2 + dp[i + 1][j - 1];
18            } else {
19                // Choose the longer subsequence
20                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
21            }
22        }
23    }
24
25    return dp[0][n - 1];
26}