Longest Decreasing Subsequence | Function that returns the length of the longest decreasing subsequence ; Initialize LDS with 1 for all index The minimum LDS starting with any element is always 1 ; Compute LDS from every index in bottom up manner ; Select the maximum of all the LDS values ; returns the length of the LDS ; Driver Code
def lds ( arr , n ) : NEW_LINE INDENT lds = [ 0 ] * n NEW_LINE max = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT lds [ i ] = 1 NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if ( arr [ i ] < arr [ j ] and lds [ i ] < lds [ j ] + 1 ) : NEW_LINE INDENT lds [ i ] = lds [ j ] + 1 NEW_LINE DEDENT DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT if ( max < lds [ i ] ) : NEW_LINE INDENT max = lds [ i ] NEW_LINE DEDENT DEDENT return max NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 15 , 27 , 14 , 38 , 63 , 55 , 46 , 65 , 85 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Length ▁ of ▁ LDS ▁ is " , lds ( arr , n ) ) NEW_LINE DEDENT