Length of longest increasing subsequence in a string | Function to find length of longest increasing subsequence in a string ; Stores at every i - th index , the length of the longest increasing subsequence ending with character i ; Size of string ; Stores the length of LIS ; Iterate over each character of the string ; Store position of the current character ; Stores the length of LIS ending with current character ; Check for all characters less then current character ; Include current character ; Update length of longest increasing subsequence ; Updating LIS for current character ; Return the length of LIS ; Driver Code
def lisOtimised ( s ) : NEW_LINE INDENT dp = [ 0 ] * 30 NEW_LINE N = len ( s ) NEW_LINE lis = - 10 ** 9 NEW_LINE for i in range ( N ) : NEW_LINE INDENT val = ord ( s [ i ] ) - ord ( ' a ' ) NEW_LINE curr = 0 NEW_LINE for j in range ( val ) : NEW_LINE INDENT curr = max ( curr , dp [ j ] ) NEW_LINE DEDENT curr += 1 NEW_LINE lis = max ( lis , curr ) NEW_LINE dp [ val ] = max ( dp [ val ] , curr ) NEW_LINE DEDENT return lis NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = " fdryutiaghfse " NEW_LINE print ( lisOtimised ( s ) ) NEW_LINE DEDENT