Longest Palindromic Subsequence | DP | 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 Code
< ? php function max ( $ x , $ y ) { return ( $ x > $ y ) ? $ x : $ y ; } function lps ( $ str ) { $ n = strlen ( $ str ) ; $ i ; $ j ; $ cl ; $ L [ ] [ ] = array ( array ( ) ) ; 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 ( $ str [ $ i ] == $ str [ $ j ] && $ cl == 2 ) $ L [ $ i ] [ $ j ] = 2 ; else if ( $ str [ $ i ] == $ str [ $ 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 ] ; } $ seq = ' EEKS FOR GEEKS ' ; $ n = strlen ( $ seq ) ; echo " The ▁ length ▁ of ▁ the ▁ " . " LPS ▁ is ▁ " , lps ( $ seq ) ; ? >