## Problem: Max and Min Products

*Difficulty: Easy

Given a set, we need to find maximum and minimum possible product among all subsets of the set.

Examples:

Input : arr[] = {4, -2, 5}; Output: Maximum product = 20 Minimum product = -40 Maximum product is obtained by multiplying 4 5 Minimum product is obtained by multiplying 4, -2, 5 Input : arr[] = {-4, -2, 3, 7, 5, 0, 1}; Output: Maximum product = 840 Minimum product = -420 Maximum product is obtained by multiplying -4, -2, 3, 7, 5 Minimum product is obtained by multiplying -4, 3, 7,

**Input:**

The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated denoting the elements of the array.

**Output:**

Print the maximum product followed by a space followed by minimum subset product.

*Constraints:*

1 ≤ T ≤ 40

1 ≤ N ≤ 20

-100 ≤ A[i] <= 100

**Example:**

*Input*

2

3

1 2 3

4

-1 -2 -3 -4

*Output*

6 1

24 -24

""" @autho: loctv @time: 09:52PM January 4, 2017 """ import itertools import operator def all_sub_sets(l): """ generate all sub sets (with length 1,2,3,....n) l: list of numbers """ bound = len(l) for i in range(1, bound+1): yield itertools.combinations(l, i) def max_min_products(l): """ find max and min product from all sub sets l: list of numbers """ max_product, min_product = -100**20, 100**20 for sub_sets in all_sub_sets(l): for sub_set in sub_sets: product = reduce(operator.mul, sub_set) if product > max_product: max_product = product if product < min_product: min_product = product print max_product, min_product if __name__ == '__main__': t = input() for _ in range(t): n = input() l = map(int, raw_input().strip().split()) max_min_products(l)

Advertisements

## Reply