Maximum Length Chain of Pairs | DP | Python program for above approach ; This function assumes that arr [ ] is sorted in increasing order according the first ( or smaller ) values in pairs . ; Initialize MCL ( max chain length ) values for all indices ; Compute optimized chain length values in bottom up manner ; Pick maximum of all MCL values ; Driver program to test above function
class Pair ( object ) : NEW_LINE INDENT def __init__ ( self , a , b ) : NEW_LINE INDENT self . a = a NEW_LINE self . b = b NEW_LINE DEDENT DEDENT def maxChainLength ( arr , n ) : NEW_LINE INDENT max = 0 NEW_LINE mcl = [ 1 for i in range ( n ) ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( 0 , i ) : NEW_LINE INDENT if ( arr [ i ] . a > arr [ j ] . b and mcl [ i ] < mcl [ j ] + 1 ) : NEW_LINE INDENT mcl [ i ] = mcl [ j ] + 1 NEW_LINE DEDENT DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT if ( max < mcl [ i ] ) : NEW_LINE INDENT max = mcl [ i ] NEW_LINE DEDENT DEDENT return max NEW_LINE DEDENT arr = [ Pair ( 5 , 24 ) , Pair ( 15 , 25 ) , Pair ( 27 , 40 ) , Pair ( 50 , 60 ) ] NEW_LINE print ( ' Length ▁ of ▁ maximum ▁ size ▁ chain ▁ is ' , maxChainLength ( arr , len ( arr ) ) ) NEW_LINE