# Longest Palindrom Subsequence via Dynamic Programming

``` /** * @author Victor Fang, 20140728 * finding longest palindrom subsequence. * there can be extra letters within. * example: BBABCBCAB has 7 char palindrom: babcbcb * * Dynamic Programming solution via Recursion: * input X[] * interim: L[i,j] = length of longest palindrom between i,j * Base 1: * L[i,i] = 1; * * Base 2: * L[i, i+1] = 2; * * Recursion: * if( X[i] == X[j] ) { L[i,j] = 2 + L[i+1, j-1] } * * if( X[i] != X[j] ) { L[i,j] = max(L[i+1, j], L[i, j-1]) } * */ public class PalindromDP { public static int max(int a, int b){ return (a>b)?a:b; }```

public static int lps(char x[], int i, int j){

// base 1: lps[]
if(i == j) return 1;
if((j == i+1) && (x[i] == x[j])) return 2;

if( x[i] == x[j]) {
return( 2 + lps(x, i+1, j-1) ) ;
}
if( x[i] != x[j]) {
return( max(lps(x, i+1, j) , lps(x, i, j-1)) );
}
return 0;

}

public static void main(String[] args) {

String x = “abigailfang”;
//String x = “BBABCBCAB”;
System.out.println(x);
System.out.println(lps(x.toCharArray(), 0, x.length()-1));
}

}

Standard