Longest increasing subsequence which forms a subarray in the sorted representation of the array | C # 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
using System . Collections . Generic ; using System ; class GFG { static int LongestSequence ( int [ ] a , int n ) { Dictionary < int , int > m = new Dictionary < int , int > ( ) ; int [ ] ar = new int [ n + 1 ] ; int i = 0 ; int j = 0 ; for ( i = 1 ; i <= n ; i ++ ) { ar [ i ] = a [ i - 1 ] ; } Array . Sort ( a ) ; int c = 1 ; m [ a [ 0 ] ] = c ; for ( i = 1 ; i < n ; i ++ ) { if ( a [ i ] != a [ i - 1 ] ) { c ++ ; m [ a [ i ] ] = c ; } } Dictionary < int , int > cnt = new Dictionary < int , int > ( ) ; int [ , ] dp = new int [ n + 1 , 3 ] ; cnt [ 0 ] = 0 ; for ( i = 1 ; i <= n ; i ++ ) { ar [ i ] = m [ ar [ i ] ] ; if ( cnt . ContainsKey ( ar [ i ] ) ) cnt [ ar [ i ] ] = cnt [ ar [ i ] ] + 1 ; else cnt [ 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 [ 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 ; } public static void Main ( ) { int [ ] arr = { 2 , 6 , 4 , 8 , 2 , 9 } ; int n = arr . Length ; Console . WriteLine ( LongestSequence ( arr , n ) ) ; } } Console . WriteLine ( LongestSequence ( arr , n ) ) ;