Maximum product of subsequence of size k | C ++ code to find maximum possible product of sub - sequence of size k from given array of n integers # include < algorithm > for sorting ; 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 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 to test above function
#include <iostream> NEW_LINE using namespace std ; int maxProductSubarrayOfSizeK ( int A [ ] , int n , int k ) { sort ( A , A + n ) ; int product = 1 ; if ( A [ n - 1 ] == 0 && ( k & 1 ) ) return 0 ; if ( A [ n - 1 ] <= 0 && ( k & 1 ) ) { for ( int i = n - 1 ; i >= n - k ; i -- ) product *= A [ i ] ; return product ; } int i = 0 ; int j = n - 1 ; if ( k & 1 ) { product *= A [ j ] ; j -- ; k -- ; } k >>= 1 ; for ( int itr = 0 ; itr < k ; itr ++ ) { int left_product = A [ i ] * A [ i + 1 ] ; int right_product = A [ j ] * A [ j - 1 ] ; if ( left_product > right_product ) { product *= left_product ; i += 2 ; } else { product *= right_product ; j -= 2 ; } } return product ; } int main ( ) { int A [ ] = { 1 , 2 , -1 , -3 , -6 , 4 } ; int n = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int k = 4 ; cout << maxProductSubarrayOfSizeK ( A , n , k ) ; return 0 ; }