Length of the longest increasing subsequence which does not contain a given sequence as Subarray | Java program for the above approach ; Initialize dp and KMP array ; Length of the given sequence [ ] ; Function to find the max - length subsequence that does not have subarray sequence [ ] ; Stores the subsequence explored so far ; Base Case ; Using memoization to avoid re - computation ; Using KMP array to find corresponding index in arr1 [ ] ; Incrementing k2 as we are including this element in the subsequence ; Possible answer for current state ; Maximum answer for current state ; Memoizing the answer for the corresponding state ; Return the answer for current state ; Function that generate KMP Array ; Previous longest prefix suffix ; KMPArray [ 0 ] is a always 0 ; The loop calculates KMPArray [ i ] for i = 1 to M - 1 ; If current character is same ; Update the KMP array ; Otherwise ; Update the KMP array ; Function to print the maximum possible length ; Length of the given sequence ; Initialize kmp array ; Generate KMP array ; Initialize dp ; Initialize the states to - 1 ; Get answer ; Print answer ; Driver code ; Given array ; Give arr1 ; Function Call
import java . io . * ; import java . util . * ; class GFG { static int [ ] [ ] [ ] dp ; static int [ ] KMPArray ; static int m ; private static int findSubsequence ( int [ ] a , int [ ] sequence , int i , int prev , int k ) { if ( k == m ) return Integer . MIN_VALUE ; if ( i == a . length ) return 0 ; if ( prev != - 1 && dp [ i ] [ prev ] [ k ] != - 1 ) { return dp [ i ] [ prev ] [ k ] ; } int include = 0 ; if ( prev == - 1 a [ i ] >= a [ prev ] ) { int k2 = k ; while ( k2 > 0 && a [ i ] != sequence [ k2 ] ) k2 = KMPArray [ k2 - 1 ] ; if ( a [ i ] == sequence [ k2 ] ) k2 ++ ; include = 1 + findSubsequence ( a , sequence , i + 1 , i , k2 ) ; } int ans = Math . max ( include , findSubsequence ( a , sequence , i + 1 , prev , k ) ) ; if ( prev != - 1 ) { dp [ i ] [ prev ] [ k ] = ans ; } return ans ; } private static void fillKMPArray ( int [ ] pattern ) { int j = 0 ; int i = 1 ; KMPArray [ 0 ] = 0 ; while ( i < m ) { if ( pattern [ i ] == pattern [ j ] ) { j ++ ; KMPArray [ i ] = j ; i ++ ; } else { if ( j != 0 ) j = KMPArray [ j - 1 ] ; else { KMPArray [ i ] = j ; i ++ ; } } } } static void printAnswer ( int a [ ] , int sequence [ ] ) { m = sequence . length ; KMPArray = new int [ m ] ; fillKMPArray ( sequence ) ; dp = new int [ a . length ] [ a . length ] [ a . length ] ; for ( int i = 0 ; i < a . length ; i ++ ) for ( int j = 0 ; j < a . length ; j ++ ) Arrays . fill ( dp [ i ] [ j ] , - 1 ) ; int ans = findSubsequence ( a , sequence , 0 , - 1 , 0 ) ; System . out . println ( ( ans < 0 ) ? 0 : ans ) ; } public static void main ( String [ ] args ) throws Exception { int [ ] arr = { 5 , 3 , 9 , 3 , 4 , 7 } ; int [ ] arr1 = { 3 , 4 } ; printAnswer ( arr , arr1 ) ; } }