DP #10. Longest Palindromic Subsequence. - mbhushan/dynpro GitHub Wiki

(10). Longest Palindromic Subsequence.

Given a sequence, find the length of the longest palindromic subsequence in it. 
For example, if the given sequence is “BBABCBCAB”, then the output should be 7 as 
“BABCBAB” is the longest palindromic subsequence in it. “BBBBB” and “BBCBB” are 
also palindromic subsequences of the given sequence, but not the longest ones.

Formula:

for (int len=2; len<=size(S); len++) { 
 for (int i=0; i<=size(S)-len; i++) {
  int j = i + len - 1;
  if (S[i] == S[j]) {
     T[i][j] = Max (T[i][j], 2 + T[i+1][j-1])
  } else {
     T[i][j] = Max (T[i][j], T[i+1][j], T[i][j-1])
  }
 }
}

Indexes		0	1	2	3	4	5	6	7	8
	Char	B	B	A	B	C	B	C	A	B
0	B	1	2	2	3	3	5	5	5	7	<- longest palindrome
1	B		1	1	3	3	5	5	5	7
2	A			1	1	1	3	3	5	5
3	B				1	1	3	3	3	5
4	C					1	1	3	3	3
5	B						1	1	1	3
6	C							1	1	1
7	A								1	1
8	B									1

public int maxPalindromicSubsequence(int [] A) {
		if (A == null || A.length < 1) {
			return 0;
		}
		int [][] dp = new int[A.length][A.length];
		
		for (int i=0; i<A.length; i++) {
			dp[i][i] = 1;
		}
		
		for (int len=2; len<=A.length; len++) {
			for (int i=0; i<=A.length-len; i++) {
				int j = i + len -1;
				if (A[i] == A[j]) {
					dp[i][j] = Math.max(dp[i][j], 2 + dp[i+1][j-1]);
				} else {
					dp[i][j] = Math.max(dp[i][j], dp[i+1][j]);
					dp[i][j] = Math.max(dp[i][j], dp[i][j-1]);
				}
			}
		}
		return dp[0][A.length-1];
	}

Longest Palindromic Sequence

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)