Length of longest increasing subsequence in a string | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int lisOtimised ( string s ) { int dp [ 30 ] = { 0 } ; int N = s . size ( ) ; int lis = INT_MIN ; for ( int i = 0 ; i < N ; i ++ ) { int val = s [ i ] - ' a ' ; int curr = 0 ; for ( int j = 0 ; j < val ; j ++ ) { curr = max ( curr , dp [ j ] ) ; } curr ++ ; lis = max ( lis , curr ) ; dp [ val ] = max ( dp [ val ] , curr ) ; } return lis ; } int main ( ) { string s = " fdryutiaghfse " ; cout << lisOtimised ( s ) ; return 0 ; }