Longest Palindromic Subsequence | DP | A Dynamic Programming based Java Program for the Egg Dropping Puzzle ; A utility function to get max of two integers ; Returns the length of the longest palindromic subsequence in seq ; Create a table to store results of subproblems ; Strings of length 1 are palindrome of lentgh 1 ; Build the table . Note that the lower diagonal values of table are useless and not filled in the process . The values are filled in a manner similar to Matrix Chain Multiplication DP solution ( Seewww . geeksforgeeks . org / matrix - chain - multiplication - dp - 8 / ) . https : cl is length of substring ; Driver program to test above functions
class LPS { static int max ( int x , int y ) { return ( x > y ) ? x : y ; } static int lps ( String seq ) { int n = seq . length ( ) ; int i , j , cl ; int L [ ] [ ] = new int [ n ] [ n ] ; for ( i = 0 ; i < n ; i ++ ) L [ i ] [ i ] = 1 ; for ( cl = 2 ; cl <= n ; cl ++ ) { for ( i = 0 ; i < n - cl + 1 ; i ++ ) { j = i + cl - 1 ; if ( seq . charAt ( i ) == seq . charAt ( j ) && cl == 2 ) L [ i ] [ j ] = 2 ; else if ( seq . charAt ( i ) == seq . charAt ( j ) ) L [ i ] [ j ] = L [ i + 1 ] [ j - 1 ] + 2 ; else L [ i ] [ j ] = max ( L [ i ] [ j - 1 ] , L [ i + 1 ] [ j ] ) ; } } return L [ 0 ] [ n - 1 ] ; } public static void main ( String args [ ] ) { String seq = " GEEKSFORGEEKS " ; int n = seq . length ( ) ; System . out . println ( " The ▁ length ▁ of ▁ the ▁ lps ▁ is ▁ " + lps ( seq ) ) ; } }