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