human
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"
Solution in Python:
 ... Give me a code to longest increasing subsequence which forms a subarray in the sorted representation of the array and the other steps required?
assistant
#Here is code to longest increasing subsequence which forms a subarray in the sorted representation of the array and the other steps required.
 def LongestSequence ( a , n ) :
	m = { i : 0 for i in range ( 100 ) }
	ar = [ 0 for i in range ( n + 1 ) ]
	for i in range ( 1 , n + 1 ) :
		ar [ i ] = a [ i - 1 ]
	a . sort ( reverse = False )
	c = 1
	m [ a [ 0 ] ] = c
	for i in range ( 1 , n ) :
		if ( a [ i ] != a [ i - 1 ] ) :
		c += 1
		m [ a [ i ] ] = c
	cnt = { i : 0 for i in range ( 100 ) }
	dp = [ [ 0 for i in range ( 3 ) ] for j in range ( n + 1 ) ]
	cnt [ 0 ] = 0
	for i in range ( 1 , n + 1 ) :
		ar [ i ] = m [ ar [ i ] ]
		cnt [ ar [ i ] ] += 1
	ans = 0
	for i in range ( 1 , n + 1 ) :
		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 ] = max ( dp [ x - 1 ] [ 0 ] , dp [ x ] [ 2 ] )
		if ( dp [ x - 1 ] [ 0 ] == cnt [ x - 1 ] ) :
			dp [ x ] [ 2 ] = max ( dp [ x ] [ 2 ] , dp [ x - 1 ] [ 1 ] )
		for j in range ( 3 ) :
			dp [ x ] [ j ] += 1
			ans = max ( ans , dp [ x ] [ j ] )
	return ans
if __name__ == ' _ _ main _ _ ' :
	arr = [ 2 , 6 , 4 , 8 , 2 , 9 ]
	N = len ( arr )
	print ( LongestSequence ( arr , N ) )