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 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
< ? php function maxProductSubarrayOfSizeK ( $ A , $ n , $ k ) { sort ( $ A ) ; $ product = 1 ; if ( $ A [ $ n - 1 ] == 0 && ( $ k & 1 ) ) return 0 ; if ( $ A [ $ n - 1 ] <= 0 && ( $ k & 1 ) ) { for ( $ i = $ n - 1 ; $ i >= $ n - $ k ; $ i -- ) $ product *= $ A [ $ i ] ; return $ product ; } $ i = 0 ; $ j = $ n - 1 ; if ( $ k & 1 ) { $ product *= $ A [ $ j ] ; $ j -- ; $ k -- ; } $ k >>= 1 ; for ( $ itr = 0 ; $ itr < $ k ; $ itr ++ ) { $ left_product = $ A [ $ i ] * $ A [ $ i + 1 ] ; $ 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 ; } $ A = array ( 1 , 2 , -1 , -3 , -6 , 4 ) ; $ n = count ( $ A ) ; $ k = 4 ; echo maxProductSubarrayOfSizeK ( $ A , $ n , $ k ) ; ? >