Given a set, we need to find the maximum and minimum possible product among all subsets of the set.
Example 1:
Input : 
arr[] = {1, 2, 3};
Output : 
Maximum product = 6
Minimum product = 1
Explanation :
Maximum product is obtained by multiplying
2, 3
Minimum product is obtained by multiplying
1
 
Example 2:
Input :
arr[] = {4, -2, 5};
Output : 
Maximum product = 20
Minimum product = -40
Explanation :
Maximum product is obtained by multiplying
4 5
Minimum product is obtained by multiplying
4, -2, 5
 
Example 3:
Input :
arr[] = {-4, -2, 3, 7, 5, 0, 1};
Output : 
Maximum product = 840
Minimum product = -420
Explanation :
Maximum product is obtained by multiplying
-4, -2, 3, 7, 5
Minimum product is obtained by multiplying
-4, 3, 7
Your Task:  
You don't need to read input or print anything. Your task is to complete the function getMaxandMinProduct() which takes the array arr[] and its size N as inputs and returns the maximum product and minimum subset product in an vector/array/list of size 2.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 20
-9 ≤ A[i] ≤ 9

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def getMaxandMinProduct(self, arr, n): 

        # Your code goes here

Solutions:
class Solution:

	def getMaxandMinProduct(self, arr, n):
		arr.sort()
		if n == 1:
			return (arr[0], arr[0])
		if n == 2 and arr[0] < 0 and (arr[1] == 0):
			return (arr[0], arr[1])
		k = 1
		lis = []
		maxa = 0
		for i in range(n):
			if arr[i] != 0:
				k *= arr[i]
			if arr[i] < 0:
				lis.append(arr[i])
		if len(lis) == 0:
			maxa = k
			mini = min(arr)
		elif len(lis) % 2 == 0:
			maxa = k
			mini = k // max(lis)
		elif len(lis) % 2 != 0:
			maxa = k // max(lis)
			mini = k
		return (mini, maxa)


class Solution:

	def getMaxandMinProduct(self, arr, n):
		arr.sort()
		(pos, neg) = ([], [])
		(neg_mul, pos_mul, zero_count) = (1, 1, 0)
		for index in range(n):
			if arr[index] < 0:
				neg.append(arr[index])
				neg_mul *= arr[index]
			elif arr[index] == 0:
				zero_count += 1
			else:
				pos = arr[index:]
				break
		for elem in pos:
			pos_mul *= elem
		if zero_count == n:
			return [0, 0]
		pos_mul = pos_mul if pos else 1
		even_neg_count = len(neg) % 2 == 0
		if not neg:
			min_ = pos[0] if not zero_count else 0
			max_ = pos_mul if pos else 0
		else:
			min_ = neg_mul // (neg[-1] if even_neg_count else 1) * pos_mul
			max_ = neg_mul // (neg[-1] if not even_neg_count else 1) * pos_mul
		if len(neg) == 1:
			max_ = pos_mul if pos else neg[0] if not zero_count else 0
		return [min_, max_]


class Solution:

	def getMaxandMinProduct(self, arr, n):
		if n == 1:
			return [arr[0], arr[0]]
		arr.sort()
		ne = 0
		p = 1
		z = 0
		c = 0
		t = None
		for i in arr:
			if i < 0:
				ne += 1
				t = i
				p *= i
				c += 1
			elif i == 0:
				z += 1
			else:
				p *= i
				c += 1
		if ne > 0:
			if p < 0:
				if c > 1:
					mx = p // t
					return [p, mx]
				elif z > 0:
					return [p, 0]
				else:
					return [p, p]
			else:
				mx = p // t
				return [mx, p]
		elif z > 0:
			return [0, p]
		else:
			return [arr[0], p]


class Solution:

	def getMaxandMinProduct(self, arr, n):
		if n == 1:
			return (arr[0], arr[0])
		curmaxp = arr[0]
		curminp = arr[0]
		prevmaxp = arr[0]
		prevminp = arr[0]
		maxp = arr[0]
		minp = arr[0]
		for i in range(1, n):
			curmaxp = max(prevmaxp * arr[i], max(prevminp * arr[i], arr[i]))
			curmaxp = max(curmaxp, prevmaxp)
			curminp = min(prevmaxp * arr[i], min(prevminp * arr[i], arr[i]))
			curminp = min(curminp, prevminp)
			maxp = max(maxp, curmaxp)
			minp = min(minp, curminp)
			prevmaxp = curmaxp
			prevminp = curminp
		return (minp, maxp)


class Solution:

	def getMaxandMinProduct(self, arr, n):
		curMaxProduct = arr[0]
		curMinProduct = arr[0]
		prevMaxProduct = arr[0]
		prevMinProduct = arr[0]
		maxProduct = arr[0]
		minProduct = arr[0]
		for i in range(1, n, 1):
			curMaxProduct = max(prevMaxProduct * arr[i], max(prevMinProduct * arr[i], arr[i]))
			curMaxProduct = max(curMaxProduct, prevMaxProduct)
			curMinProduct = min(prevMaxProduct * arr[i], min(prevMinProduct * arr[i], arr[i]))
			curMinProduct = min(curMinProduct, prevMinProduct)
			maxProduct = max(maxProduct, curMaxProduct)
			minProduct = min(minProduct, curMinProduct)
			prevMaxProduct = curMaxProduct
			prevMinProduct = curMinProduct
		return (minProduct, maxProduct)


class Solution:

	def getMaxandMinProduct(self, a, n):
		if n == 1:
			return (a[0], a[0])
		if n == 2 and (a[0] <= 0 or a[1] <= 0):
			return (min(a), max(a))
		b = []
		k = 1
		m = 1
		for i in range(len(a)):
			if a[i] > 0:
				k *= a[i]
			elif a[i] < 0:
				b.append(a[i])
		if len(b) == 0:
			m = min(a)
			return (m, k)
		elif len(b) % 2 != 0:
			for i in range(len(b)):
				m *= b[i]
			m *= k
			k = m
			k = k // max(b)
		else:
			minb = max(b)
			for i in range(len(b)):
				k *= b[i]
			m = k
			m = m // minb
		return (m, k)


class Solution:

	def getMaxandMinProduct(self, arr, n):
		if n == 1:
			return (arr[0], arr[0])
		negMax = -10000000000
		negcnt = 0
		posCnt = 0
		product = 1
		for elem in arr:
			if elem < 0:
				negcnt += 1
				negMax = max(negMax, elem)
			if elem != 0:
				product *= elem
			if elem > 0:
				posCnt += 1
		if posCnt == 0 and n - posCnt - negcnt != 0:
			if negcnt % 2 == 0:
				return (int(product / negMax), 0)
			return (product, 0)
		if negcnt == 0:
			return (min(arr), product)
		if negcnt % 2 == 0:
			return (int(product / negMax), product)
		return (product, int(product / negMax))


class Solution:

	def getMaxandMinProduct(self, arr, n):
		curx = arr[0]
		curin = arr[0]
		minn = arr[0]
		maxx = arr[0]
		i = 1
		while i < n:
			if curx < 1:
				curx = 1
			if curin > -1:
				curin = 1
			curx *= arr[i]
			curin *= arr[i]
			maxx = max(maxx, max(curx, curin))
			minn = min(minn, min(curx, curin))
			curx = max(curx, max(curin, maxx))
			curin = min(curin, min(curx, minn))
			i += 1
		return [minn, maxx]


class Solution:

	def getMaxandMinProduct(self, arr, n):
		POS_INFINITY = 100000000
		smallestNeg = POS_INFINITY
		(negatives, positives, zeros, product) = (0, 0, 0, 1)
		for i in arr:
			if i == 0:
				zeros += 1
			elif i > 0:
				positives += 1
			else:
				negatives += 1
				if abs(i) < smallestNeg:
					smallestNeg = abs(i)
			if i != 0:
				product *= i
		(maximum, minimum) = (0, 0)
		if negatives == 0 and positives == 0:
			(maximum, minimum) = (0, 0)
		elif product > 0:
			maximum = product
			if negatives == 0:
				minimum = min(arr)
			else:
				minimum = -1 * (product // smallestNeg)
		elif product < 0:
			minimum = product
			if negatives == 1 and len(arr) == 1:
				maximum = arr[0]
			elif negatives == 1:
				if positives == 0:
					maximum = 0
				else:
					maximum = abs(product) // smallestNeg
			else:
				maximum = abs(product) // smallestNeg
		return [minimum, maximum]


class Solution:

	def getMaxandMinProduct(self, arr, n):
		neg = 0
		min_neg = float('-inf')
		min_pos = float('inf')
		pos_prod = 1
		neg_prod = 1
		pos = 0
		is_zero = False
		for ele in arr:
			if ele == 0:
				is_zero = True
			elif ele < 0:
				neg += 1
				neg_prod *= ele
				min_neg = max(min_neg, ele)
			elif ele > 0:
				pos += 1
				min_pos = min(min_pos, ele)
				pos_prod *= ele
		if neg == 0:
			min_prod = min_pos
			if is_zero:
				min_prod = 0
			max_prod = pos_prod
		elif pos == 0:
			max_prod = min_neg
			if is_zero:
				max_prod = 0
			min_prod = neg_prod
			if neg % 2 == 0:
				min_prod = min_prod // min_neg
		elif neg == n:
			min_prod = min_neg
			max_prod = neg_prod
		elif neg % 2 == 0:
			max_prod = pos_prod * neg_prod
			min_prod = max_prod // min_neg
		else:
			min_prod = pos_prod * neg_prod
			max_prod = min_prod // min_neg
		return [min_prod, max_prod]