Given an array arr[] of N integers, the task is to find a subsequence of size K whose product is maximum among all possible K sized subsequences of a given array.
Example 1:
Input: N = 4, K = 2
arr[] = {1, 2, 0, 3} 
Output: 6
Explanation: Subsequence containing 
elements {2, 3} gives maximum product: 
2*3 = 6
Example 2:
Input: N = 6, K = 4
arr[] = {1, 2, -1, -3, -6, 4}
Output: 144
Explanation: Subsequence containing 
{2, -3, -6, 4} gives maximum product: 
2*(-3)*(-6)*4 = 144
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function maxProductSubarrayOfSizeK() that takes array arr[], integer N and integer K as parameters and returns the desired product.
 
Expected Time Complexity: O(NlogN).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: class Solution:
    def maxProductSubarrayOfSizeK(self,arr, n, k):
        # Your code goes here

Solutions:
class Solution:

	def maxProductSubarrayOfSizeK(self, arr, n, k):
		product = 1
		arr.sort()
		if k % 2 and arr[-1] < 0:
			for _ in range(k):
				product *= arr.pop()
			return product
		if k % 2:
			product *= arr.pop()
			k -= 1
		while k:
			if arr[0] * arr[1] > arr[-1] * arr[-2]:
				product *= arr.pop(0) * arr.pop(0)
			else:
				product *= arr.pop() * arr.pop()
			k -= 2
		return product


class Solution:

	def maxProductSubarrayOfSizeK(self, arr, n, k):
		arr.sort()
		if k == 1:
			return arr[-1]
		if arr[-1] == 0:
			return 0
		arr_len = len(arr)
		if k % 2 == 0:
			remainder = 0
			even_k = k
		else:
			remainder = 1
			even_k = k - 1
		i = 0
		j = len(arr) - 1
		subsequence = [None] * k
		subsequence_index = 0
		prod = 1
		if arr[-1] < 0:
			if not remainder:
				for i in range(0, k):
					subsequence[subsequence_index] = i
					subsequence_index += 1
					prod *= arr[i]
			else:
				for i in range(arr_len - k, arr_len):
					subsequence[subsequence_index] = i
					subsequence_index += 1
					prod *= arr[i]
			return prod
		subsequence_lenght = 0
		max_prod = 1
		if remainder:
			subsequence[-1] = j
			j -= 1
		while subsequence_lenght < even_k:
			if arr[i] * arr[i + 1] > arr[j] * arr[j - 1]:
				subsequence[i] = i
				subsequence[i + 1] = i + 1
				max_prod *= arr[i] * arr[i + 1]
				i += 2
			else:
				subsequence[k - (arr_len - j)] = j
				subsequence[k - (arr_len - j) - 1] = j - 1
				j -= 2
				max_prod *= arr[j] * arr[j - 1]
			subsequence_lenght += 2
		max_prod2 = 1
		for item in subsequence:
			max_prod2 *= arr[item]
		return max_prod2


class Solution:

	def maxProductSubarrayOfSizeK(self, arr, n, k):
		ans = 1
		arr.sort()
		if arr[n - 1] == 0 and k & 1:
			return 0
		if arr[n - 1] < 0 and k & 1:
			temp = 1
			i = n - 1
			while i >= n - k:
				temp *= arr[i]
				i -= 1
			return temp
		(i, j) = (0, n - 1)
		if arr[j] > 0 and k & 1:
			ans *= arr[j]
			k -= 1
			j -= 1
		while i <= j and k:
			p1 = arr[i] * arr[i + 1]
			p2 = arr[j] * arr[j - 1]
			if p1 > p2:
				ans *= p1
				i += 2
				k -= 2
			else:
				ans *= p2
				j -= 2
				k -= 2
		return ans


class Solution:

	def maxProductSubarrayOfSizeK(self, arr, n, k):
		arr.sort()
		ma = max(arr)
		if k % 2 == 0:
			p = 1
			l = 0
			r = n - 1
			for j in range(k // 2):
				a = arr[l] * arr[l + 1]
				b = arr[r] * arr[r - 1]
				if a >= b:
					p *= a
					l += 2
				else:
					p *= b
					r -= 2
		elif ma < 0:
			arr.sort(reverse=True)
			lst = arr[:k]
			p = 1
			for j in lst:
				p *= j
		elif ma == 0:
			p = 0
		else:
			p = ma
			k -= 1
			l = 0
			arr = arr[:n - 1]
			r = n - 2
			for j in range(k // 2):
				a = arr[l] * arr[l + 1]
				b = arr[r] * arr[r - 1]
				if a >= b:
					p *= a
					l += 2
				else:
					p *= b
					r -= 2
		return p


class Solution:

	def maxProductSubarrayOfSizeK(self, arr, n, k):
		arr.sort()
		A = arr
		A.sort()
		product = 1
		if A[n - 1] == 0 and k & 1:
			return 0
		if A[n - 1] <= 0 and k & 1:
			i = n - 1
			while k > 0:
				product *= A[i]
				k -= 1
				i -= 1
			return product
		i = 0
		j = n - 1
		if k & 1:
			product *= A[j]
			j -= 1
			k -= 1
		k >>= 1
		for itr in range(k):
			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