Longest Palindromic Subsequence | DP | A utility function to get max of two integers ; Returns the length of the longest palindromic subsequence in seq ; Base Case 1 : If there is only 1 character ; Base Case 2 : If there are only 2 characters and both are same ; If the first and last characters match ; If the first and last characters do not match ; Driver Code
def max ( x , y ) : NEW_LINE INDENT if ( x > y ) : NEW_LINE INDENT return x NEW_LINE DEDENT return y NEW_LINE DEDENT def lps ( seq , i , j ) : NEW_LINE INDENT if ( i == j ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( seq [ i ] == seq [ j ] and i + 1 == j ) : NEW_LINE INDENT return 2 NEW_LINE DEDENT if ( seq [ i ] == seq [ j ] ) : NEW_LINE INDENT return lps ( seq , i + 1 , j - 1 ) + 2 NEW_LINE DEDENT return max ( lps ( seq , i , j - 1 ) , lps ( seq , i + 1 , j ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT seq = " GEEKSFORGEEKS " NEW_LINE n = len ( seq ) NEW_LINE print ( " The ▁ length ▁ of ▁ the ▁ LPS ▁ is " , lps ( seq , 0 , n - 1 ) ) NEW_LINE DEDENT