Longest increasing subsequence which forms a subarray in the sorted representation of the array | 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
function LongestSequence ( a , n ) { var m = new Map ( ) ; var ar = Array ( n + 1 ) . fill ( 0 ) , i , j ; for ( i = 1 ; i <= n ; i ++ ) { ar [ i ] = a [ i - 1 ] ; } a . sort ( ( a , b ) => a - b ) ; var c = 1 ; m . set ( a [ 0 ] , c ) ; for ( i = 1 ; i <= n ; i ++ ) { if ( a [ i ] != a [ i - 1 ] ) { c ++ ; m . set ( a [ i ] , c ) ; } } var cnt = new Map ( ) ; var dp = Array . from ( Array ( n + 1 ) , ( ) => Array ( 3 ) . fill ( 0 ) ) ; cnt . set ( 0 , 0 ) ; for ( i = 1 ; i <= n ; i ++ ) { ar [ i ] = m . get ( ar [ i ] ) ; if ( cnt . has ( ar [ i ] ) ) cnt . set ( ar [ i ] , cnt . get ( ar [ i ] ) + 1 ) else cnt . set ( ar [ i ] , 1 ) } var 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 [ 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 ; } var arr = [ 2 , 6 , 4 , 8 , 2 , 9 ] ; var N = arr . length ; document . write ( LongestSequence ( arr , N ) ) ;