Refactor the code which performs "cross-product", "reduce", "product of list" and "sum of list" I have come up with a sequence of steps to find the maximum product of y positive numbers which add up to x. But the program is highly inefficient.

Here's my code:

from itertools import product
from functools import reduce
from operator import mul

for i in range(int(input())):               # &lt;-- number of pairs of input
    lgr = 1
    k = set()
    x, y = tuple(map(int, input().split())) #  &lt;-- the input pairs
    p = product(range(1, x+1), repeat=y)    #  &lt;-- gets the cross product
    for i in p:
        if sum(i) == x:                     #  &lt;-- checks if sum is equal to x
            k.add(i)                        #  &lt;-- adds it to a set() to remove duplicates
    for i in k:
        tmp = reduce(mul, i, 1)             #  &lt;-- multiplies the items in the tuple to get the largest
        if tmp &gt; lgr:
            lgr = tmp
    print(lgr)


But say for an input like 14 7 it just takes too long (around 20s). Is there a better way to do it?

Update 1:
I've managed to improve a bit by using combinations_with_replacement and set &amp; list comprehension... but I believe it can be done better... any suggestions...?

from itertools import combinations_with_replacement
from functools import reduce
from operator import mul

for i in range(int(input())):
    lgr = 1
    x, y = tuple(map(int, input().split()))
    k = {i for i in combinations_with_replacement(range(1, x+1), y) if sum(i) == x}
    lgr = max([max(reduce(mul, i, 1), lgr) for i in k])
    print(lgr)
One immediate improvement is realizing that for e.g the input 14 7, all combinations like x x x x x x 9 and above can never sum to 14, because even for the minimal case x = 1, 9 + 6*1 = 15. So you can vastly reduce the number of combinations you need to check by using 

k = {i for i in combinations_with_replacement(range(1, x - y + 2), y) if sum(i) == x}


For the input 14 7 this constitutes a difference of 77520 possible combinations down to 3432.

This adds a constraint only on the last number, but you could take this to its logical extreme and write code that always aborts the combinations once the sum has been reached.

One other thing you should do is use better names and use functions. I have no idea that k is a list of combinations of numbers, or what this means. Also, using i (and j, k, n, too, for that matter) for anything other than an integer is not helpful either.

I would at least rewrite your code to this:

from itertools import combinations_with_replacement
try:  # Python 3.8+
    from math import prod
except ImportError:
    from functools import reduce
    from operator import mul
    def prod(x):
        """Returns the product of all elements of `x`, similar to `sum`."""
        return reduce(mul, x, 1)

def maximum_product_with_sum(x, n):
    """Return the maximum product of all `n` positive numbers that sum to `x`."""
    r = range(1, x - n + 2)
    candidates = {candidate 
                  for candidate in combinations_with_replacement(r, n)
                  if sum(candidate) == x}
    return max(map(prod, candidates), default=1)

if __name__ == "__main__":
    for _ in range(int(input())):
        x, n = tuple(map(int, input().split()))
        print(maximum_product_with_sum(x, n))


Note that I also added some short docstrings to describe what each function does and simplified getting the maximum, your inner call to max was not needed. The optional keyword argument argument default of max is the default value if the iterable is empty.

I also added a if __name__ == "__main__": guard to allow importing from this script from another script without the code being run.

Here is the performance measured against your second function (the first one is way too slow) once for the input x 7 and once for 14 n:



You can see that this code is not only faster in general, it also becomes much faster if n &gt; x / 2.