Maximize subsequences having array elements not exceeding length of the subsequence | Python3 program for the above approach ; Function to calculate the number of subsequences that can be formed ; Stores the number of subsequences ; Iterate over the map ; Count the number of subsequences that can be formed from x . first ; Number of occurrences of x . first which are left ; Return the number of subsequences ; Function to create the maximum count of subsequences that can be formed ; Stores the frequency of arr [ ] ; Update the frequency ; Print the number of subsequences ; Driver Code ; Given array arr [ ] ; Function Call
from collections import defaultdict NEW_LINE def No_Of_subsequences ( mp ) : NEW_LINE INDENT count = 0 NEW_LINE left = 0 NEW_LINE for x in mp : NEW_LINE INDENT mp [ x ] += left NEW_LINE count += ( mp [ x ] // x ) NEW_LINE left = mp [ x ] % x NEW_LINE DEDENT return count NEW_LINE DEDENT def maximumsubsequences ( arr , n ) : NEW_LINE INDENT mp = defaultdict ( int ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT mp [ arr [ i ] ] += 1 NEW_LINE DEDENT print ( No_Of_subsequences ( mp ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 1 , 1 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE maximumsubsequences ( arr , N ) NEW_LINE DEDENT