Longest increasing subsequence which forms a subarray in the sorted representation of the array | Java program to implement the above approach ; Function to find the length of the longest increasing sorted sequence ; Stores the count of all elements ; Store the original array ; Sort the array ; If adjacent element are not same ; Increment count ; Store frequency of each element ; Initialize a DP array ; Iterate over the array ar [ ] ; Length of the longest increasing sorted sequence ; Iterate over the array ; Current element ; If the element has been encountered the first time ; If all the x - 1 previous elements have already appeared ; Otherwise ; If all x - 1 elements have already been encountered ; Increment the count of the current element ; Update maximum subsequence size ; Return the maximum subsequence size ; Driver code ; Function Call
import java . io . * ; import java . util . * ; class GFG { static int LongestSequence ( int a [ ] , int n ) { HashMap < Integer , Integer > m = new HashMap < > ( ) ; int ar [ ] = new int [ n + 1 ] ; int i = 0 ; int j = 0 ; for ( i = 1 ; i <= n ; i ++ ) { ar [ i ] = a [ i - 1 ] ; } Arrays . sort ( a ) ; int c = 1 ; m . put ( a [ 0 ] , c ) ; for ( i = 1 ; i < n ; i ++ ) { if ( a [ i ] != a [ i - 1 ] ) { c ++ ; m . put ( a [ i ] , c ) ; } } HashMap < Integer , Integer > cnt = new HashMap < > ( ) ; int dp [ ] [ ] = new int [ n + 1 ] [ 3 ] ; cnt . put ( 0 , 0 ) ; for ( i = 1 ; i <= n ; i ++ ) { ar [ i ] = m . get ( ar [ i ] ) ; if ( cnt . containsKey ( ar [ i ] ) ) cnt . put ( ar [ i ] , cnt . get ( ar [ i ] ) + 1 ) ; else cnt . put ( ar [ i ] , 1 ) ; } int ans = 0 , x ; for ( i = 1 ; i <= n ; i ++ ) { x = ar [ i ] ; if ( dp [ x ] [ 0 ] == 0 ) { if ( dp [ x - 1 ] [ 0 ] == cnt . get ( x - 1 ) ) { dp [ x ] [ 1 ] = dp [ x - 1 ] [ 1 ] ; dp [ x ] [ 2 ] = dp [ x - 1 ] [ 1 ] ; } else { dp [ x ] [ 1 ] = dp [ x - 1 ] [ 0 ] ; } } dp [ x ] [ 2 ] = Math . max ( dp [ x - 1 ] [ 0 ] , dp [ x ] [ 2 ] ) ; if ( dp [ x - 1 ] [ 0 ] == cnt . get ( x - 1 ) ) { dp [ x ] [ 2 ] = Math . max ( dp [ x ] [ 2 ] , dp [ x - 1 ] [ 1 ] ) ; } for ( j = 0 ; j < 3 ; j ++ ) { dp [ x ] [ j ] ++ ; ans = Math . max ( ans , dp [ x ] [ j ] ) ; } } return ans ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 6 , 4 , 8 , 2 , 9 } ; int n = arr . length ; System . out . println ( LongestSequence ( arr , n ) ) ; } } System . out . println ( LongestSequence ( arr , n ) ) ; }