Find the value of max ( f ( x ) ) | Python 3 implementation of above approach ; Function to calculate the value ; forming the prefix sum arrays ; Taking the query ; finding the sum in the range l to r in array a ; finding the sum in the range l to r in array b ; Finding the max value of the function ; Finding the min value of the function ; Driver code
MAX = 200006 NEW_LINE CONS = 32766 NEW_LINE def calc ( a , b , lr , q , n ) : NEW_LINE INDENT cc = 0 NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT a [ i + 1 ] += a [ i ] NEW_LINE b [ i + 1 ] += b [ i ] NEW_LINE DEDENT while ( q > 0 ) : NEW_LINE INDENT l = lr [ cc ] NEW_LINE cc += 1 NEW_LINE r = lr [ cc ] NEW_LINE cc += 1 NEW_LINE l -= 2 NEW_LINE r -= 1 NEW_LINE suma = a [ r ] NEW_LINE sumb = b [ r ] NEW_LINE if ( l >= 0 ) : NEW_LINE INDENT suma -= a [ l ] NEW_LINE sumb -= b [ l ] NEW_LINE DEDENT M = max ( CONS * suma + CONS * sumb , - CONS * suma - CONS * sumb ) NEW_LINE M = max ( M , max ( CONS * suma - CONS * sumb , - CONS * suma + CONS * sumb ) ) NEW_LINE m = min ( CONS * suma + CONS * sumb , - CONS * suma - CONS * sumb ) NEW_LINE m = min ( m , min ( CONS * suma - CONS * sumb , - CONS * suma + CONS * sumb ) ) NEW_LINE print ( M - m ) NEW_LINE q -= 1 NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 NEW_LINE q = 2 NEW_LINE a = [ 0 , 7 , 3 , 4 , 5 ] NEW_LINE b = [ 0 , 3 , 1 , 2 , 3 ] NEW_LINE lr = [ 0 ] * ( q * 2 ) NEW_LINE lr [ 0 ] = 1 NEW_LINE lr [ 1 ] = 1 NEW_LINE lr [ 2 ] = 1 NEW_LINE lr [ 3 ] = 3 NEW_LINE calc ( a , b , lr , q , n ) NEW_LINE DEDENT