Longest permutation subsequence in a given array | Program to find length of Longest Permutation Subsequence in a given array ; Function to find the longest permutation subsequence ; Map data structure to count the frequency of each element ; If frequency of element is 0 , then we can not move forward as every element should be present ; Increasing the length by one ; Driver Code
from collections import defaultdict NEW_LINE def longestPermutation ( a , n ) : NEW_LINE INDENT freq = defaultdict ( int ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT freq [ a [ i ] ] += 1 NEW_LINE DEDENT length = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( freq [ i ] == 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT length += 1 NEW_LINE DEDENT return length NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 3 , 2 , 1 , 6 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE print ( longestPermutation ( arr , n ) ) NEW_LINE DEDENT