Longest Palindromic Subsequence

Problem: Given a string, find the longest palindromic subsequence possible. 

Basic idea is to divide the problem in subproblems. 

1. Start with a substring of length 1 and then 2 and 3 and so on.
2. As we are solving the sub problems store them in a matrix.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

public int longestPalindSubSequence(String s){ char[] str = s.toCharArray(); int[][] T = new int[s.length()][s.length()]; for(int i=0; i<s.length(); i++){ for(int j=0; j<s.length(); j++){ if(i==j){ T[i][j] =1; } } } for(int i = 0; i < s.length(); i++){ for(int j=0; j < s.length()-i-1; j++){ if(str[j]== str[i+j+1]){ T[j][j+i+1] = 2 + T[j+1][i+j]; }else{ T[j][j+i+1] = Math.max(T[j+1][j+i+1], T[j][j+i]); } } } //test to see the result matrix; for(int i=0; i < T.length; i++){ for(int j=0; j< T[i].length; j++){ System.out.print(T[i][j]); } System.out.println(); } return T[0][s.length()-1]; } public int recursivePalindSubSeq(String s, int start, int len){ if(len == 1){ return 1; } if(len ==0){ return 0; } if(s.charAt(start) == s.charAt(start+len-1)){ return 2+ recursivePalindSubSeq(s, start+1, len-2); }else{ return Math.max(recursivePalindSubSeq(s, start+1, len-1), recursivePalindSubSeq(s, start, len-2)); } }