Length of longest increasing subsequence in a string | Java program for the above approach ; 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
import java . util . * ; class GFG { static int mn = - 2147483648 ; static int lisOtimised ( String s ) { int [ ] dp = new int [ 30 ] ; Arrays . fill ( dp , 0 ) ; int N = s . length ( ) ; int lis = mn ; for ( int i = 0 ; i < N ; i ++ ) { int val = ( int ) s . charAt ( i ) - 97 ; int curr = 0 ; for ( int j = 0 ; j < val ; j ++ ) { curr = Math . max ( curr , dp [ j ] ) ; } curr ++ ; lis = Math . max ( lis , curr ) ; dp [ val ] = Math . max ( dp [ val ] , curr ) ; } return lis ; } public static void main ( String [ ] args ) { String s = " fdryutiaghfse " ; System . out . print ( lisOtimised ( s ) ) ; } }