Maximum product of a triplet ( subsequence of size 3 ) in array | A Python3 program to find a maximum product of a triplet in array of integers ; Function to find a maximum product of a triplet in array of integers of size n ; If size is less than 3 , no triplet exists ; Construct four auxiliary vectors of size n and initialize them by - 1 ; Will contain max product ; To store maximum element on left of array ; To store minimum element on left of array ; leftMax [ i ] will contain max element on left of arr [ i ] excluding arr [ i ] . leftMin [ i ] will contain min element on left of arr [ i ] excluding arr [ i ] . ; Reset max_sum to store maximum element on right of array ; Reset min_sum to store minimum element on right of array ; rightMax [ i ] will contain max element on right of arr [ i ] excluding arr [ i ] . rightMin [ i ] will contain min element on right of arr [ i ] excluding arr [ i ] . ; For all array indexes i except first and last , compute maximum of arr [ i ] * x * y where x can be leftMax [ i ] or leftMin [ i ] and y can be rightMax [ i ] or rightMin [ i ] . ; Driver code
import sys NEW_LINE def maxProduct ( arr , n ) : NEW_LINE INDENT if ( n < 3 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT leftMin = [ - 1 for i in range ( n ) ] NEW_LINE rightMin = [ - 1 for i in range ( n ) ] NEW_LINE leftMax = [ - 1 for i in range ( n ) ] NEW_LINE rightMax = [ - 1 for i in range ( n ) ] NEW_LINE max_product = - sys . maxsize - 1 NEW_LINE max_sum = arr [ 0 ] NEW_LINE min_sum = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT leftMax [ i ] = max_sum NEW_LINE if ( arr [ i ] > max_sum ) : NEW_LINE INDENT max_sum = arr [ i ] NEW_LINE DEDENT leftMin [ i ] = min_sum NEW_LINE if ( arr [ i ] < min_sum ) : NEW_LINE INDENT min_sum = arr [ i ] NEW_LINE DEDENT DEDENT max_sum = arr [ n - 1 ] NEW_LINE min_sum = arr [ n - 1 ] NEW_LINE for j in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT rightMax [ j ] = max_sum NEW_LINE if ( arr [ j ] > max_sum ) : NEW_LINE INDENT max_sum = arr [ j ] NEW_LINE DEDENT rightMin [ j ] = min_sum NEW_LINE if ( arr [ j ] < min_sum ) : NEW_LINE INDENT min_sum = arr [ j ] NEW_LINE DEDENT DEDENT for i in range ( 1 , n - 1 ) : NEW_LINE INDENT max1 = max ( arr [ i ] * leftMax [ i ] * rightMax [ i ] , arr [ i ] * leftMin [ i ] * rightMin [ i ] ) NEW_LINE max2 = max ( arr [ i ] * leftMax [ i ] * rightMin [ i ] , arr [ i ] * leftMin [ i ] * rightMax [ i ] ) NEW_LINE max_product = max ( max_product , max ( max1 , max2 ) ) NEW_LINE DEDENT return max_product NEW_LINE DEDENT arr = [ 1 , 4 , 3 , - 6 , - 7 , 0 ] NEW_LINE n = len ( arr ) NEW_LINE Max = maxProduct ( arr , n ) NEW_LINE if ( Max == - 1 ) : NEW_LINE INDENT print ( " No ▁ Triplet ▁ Exists " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Maximum ▁ product ▁ is " , Max ) NEW_LINE DEDENT