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
def LongestSequence ( a , n ) : NEW_LINE INDENT m = { i : 0 for i in range ( 100 ) } NEW_LINE ar = [ 0 for i in range ( n + 1 ) ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT ar [ i ] = a [ i - 1 ] NEW_LINE DEDENT a . sort ( reverse = False ) NEW_LINE c = 1 NEW_LINE m [ a [ 0 ] ] = c NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( a [ i ] != a [ i - 1 ] ) : NEW_LINE c += 1 NEW_LINE m [ a [ i ] ] = c NEW_LINE DEDENT cnt = { i : 0 for i in range ( 100 ) } NEW_LINE dp = [ [ 0 for i in range ( 3 ) ] for j in range ( n + 1 ) ] NEW_LINE cnt [ 0 ] = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT ar [ i ] = m [ ar [ i ] ] NEW_LINE cnt [ ar [ i ] ] += 1 NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT x = ar [ i ] NEW_LINE if ( dp [ x ] [ 0 ] == 0 ) : NEW_LINE if ( dp [ x - 1 ] [ 0 ] == cnt [ x - 1 ] ) : NEW_LINE INDENT dp [ x ] [ 1 ] = dp [ x - 1 ] [ 1 ] NEW_LINE dp [ x ] [ 2 ] = dp [ x - 1 ] [ 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ x ] [ 1 ] = dp [ x - 1 ] [ 0 ] NEW_LINE DEDENT dp [ x ] [ 2 ] = max ( dp [ x - 1 ] [ 0 ] , dp [ x ] [ 2 ] ) NEW_LINE if ( dp [ x - 1 ] [ 0 ] == cnt [ x - 1 ] ) : NEW_LINE INDENT dp [ x ] [ 2 ] = max ( dp [ x ] [ 2 ] , dp [ x - 1 ] [ 1 ] ) NEW_LINE DEDENT for j in range ( 3 ) : NEW_LINE INDENT dp [ x ] [ j ] += 1 NEW_LINE ans = max ( ans , dp [ x ] [ j ] ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 6 , 4 , 8 , 2 , 9 ] NEW_LINE N = len ( arr ) NEW_LINE print ( LongestSequence ( arr , N ) ) NEW_LINE DEDENT