Minimize prize count required such that smaller value gets less prize in an adjacent pair | Function to find the minimum number of required such that adjacent smaller elements gets less number of prizes ; Loop to compute the smaller elements at the left ; Loop to find the smaller elements at the right ; Loop to find the minimum prizes required ; Driver code
def minPrizes ( arr , n ) : NEW_LINE INDENT dpLeft = [ 0 ] * n NEW_LINE dpLeft [ 0 ] = 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if arr [ i ] > arr [ i - 1 ] : NEW_LINE INDENT dpLeft [ i ] = dpLeft [ i - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT dpLeft [ i ] = 1 NEW_LINE DEDENT DEDENT dpRight = [ 0 ] * n NEW_LINE dpRight [ - 1 ] = 1 NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT if arr [ i ] > arr [ i + 1 ] : NEW_LINE INDENT dpRight [ i ] = dpRight [ i + 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT dpRight [ i ] = 1 NEW_LINE DEDENT DEDENT totalPrizes = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT totalPrizes += max ( dpLeft [ i ] , dpRight [ i ] ) NEW_LINE DEDENT print ( totalPrizes ) NEW_LINE DEDENT arr = [ 1 , 2 , 2 , 3 ] NEW_LINE n = len ( arr ) NEW_LINE minPrizes ( arr , n ) NEW_LINE