Maximum product of subsequence of size k | Required function ; sorting given input array ; variable to store final product of all element of sub - sequence of size k ; CASE I If max element is 0 and k is odd then max product will be 0 ; CASE II If all elements are negative and k is odd then max product will be product of rightmost - subarray of size k ; else i is current left pointer index ; j is current right pointer index ; CASE III if k is odd and rightmost element in sorted array is positive then it must come in subsequence Multiplying A [ j ] with product and correspondingly changing j ; CASE IV Now k is even . So , Now we deal with pairs Each time a pair is multiplied to product ie . . two elements are added to subsequence each time . Effectively k becomes half Hence , k >>= 1 means k /= 2 ; Now finding k corresponding pairs to get maximum possible value of product ; product from left pointers ; product from right pointers ; Taking the max product from two choices . Correspondingly changing the pointer 's position ; Finally return product ; Driver Code
def maxProductSubarrayOfSizeK ( A , n , k ) : NEW_LINE INDENT A . sort ( ) NEW_LINE product = 1 NEW_LINE if ( A [ n - 1 ] == 0 and ( k & 1 ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( A [ n - 1 ] <= 0 and ( k & 1 ) ) : NEW_LINE INDENT for i in range ( n - 1 , n - k + 1 , - 1 ) : NEW_LINE INDENT product *= A [ i ] NEW_LINE DEDENT return product NEW_LINE DEDENT i = 0 NEW_LINE j = n - 1 NEW_LINE if ( k & 1 ) : NEW_LINE INDENT product *= A [ j ] NEW_LINE j -= 1 NEW_LINE k -= 1 NEW_LINE DEDENT k >>= 1 NEW_LINE for itr in range ( k ) : NEW_LINE INDENT left_product = A [ i ] * A [ i + 1 ] NEW_LINE right_product = A [ j ] * A [ j - 1 ] NEW_LINE if ( left_product > right_product ) : NEW_LINE INDENT product *= left_product NEW_LINE i += 2 NEW_LINE DEDENT else : NEW_LINE INDENT product *= right_product NEW_LINE j -= 2 NEW_LINE DEDENT DEDENT return product NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 1 , 2 , - 1 , - 3 , - 6 , 4 ] NEW_LINE n = len ( A ) NEW_LINE k = 4 NEW_LINE print ( maxProductSubarrayOfSizeK ( A , n , k ) ) NEW_LINE DEDENT