Maximum product of integers from an array-CodePudding

Trying out a question where I'm calculating the max product possible from any integers in an array.

I've written something that works for some tests, but fails others.

def solution(xs):
    if len(xs) == 1:
        return xs[0]
    v = 1
    s = -1001
    nn = 0
    for i in xs:
        if i < 0:
            nn  = 1
            if i > s:
                s = i
        if i != 0:
            v *= i
    if nn % 2 == 1:
        v /= s
    return str(v)

My theory was the maximum product could be calculated by looping through an array, multiplying each number together and then in the case of an odd number of negative numbers, divide by the largest negative.

I'm missing something, but I'm not exactly sure what.

BTW The seemingly arbitrary choice of -1001 is the limit set by the test cases.

CodePudding user response：

This should work:

import math


def max_product(arr, num):
    pos_sorted = sorted([element for element in arr if element > 0])
    neg_sorted = sorted([element for element in arr if element < 0], reverse=True)
    factors = []

    if num % 2:
        factors.append(pos_sorted.pop())
        num -= 1

    while num > 0:
        if pos_sorted[-1] * pos_sorted[-2] > neg_sorted[-1] * neg_sorted[-2]:
            factors.append(pos_sorted.pop())
            factors.append(pos_sorted.pop())
        else:
            factors.append(neg_sorted.pop())
            factors.append(neg_sorted.pop())
        num -= 2
    return math.prod(factors), factors


arr = [-10, 1, 2, 9, -3, 5, -2, 3, 17, 5, -2, -9, -18]
print(max_product(arr, 1))
print(max_product(arr, 2))
print(max_product(arr, 3))
print(max_product(arr, 4))
print(max_product(arr, 5))
print(max_product(arr, 6))
print(max_product(arr, 7))
print(max_product(arr, 8))

Output:

(17, [17])
(180, [-18, -10])
(3060, [17, -18, -10])
(27540, [-18, -10, 17, 9])
(137700, [17, -18, -10, 9, 5])
(743580, [-18, -10, 17, 9, -9, -3])
(3717900, [17, -18, -10, 9, 5, -9, -3])
(18589500, [-18, -10, 17, 9, -9, -3, 5, 5])

The explanation:

If you have an odd number, you first take the highest value from the pos-list, as for an odd number there must be at least one positive.
Then you take pairwise two negative or two positive numbers whichever has the higher product. The reason for that is, that you can't just take one negative as then the result would be negative. But you can't just take one positive either, as then there would be an odd number of values left of which one has to be positive, so you can take that already.

If you exhaust all your negative or positive numbers, or there are not enough to begin with, you could run into KeyErrors in the if-statement. But this can be easily checked and is left as a homework for the reader :).

CodePudding user response：

So I ended up rewriting the solution to incorporate a handful of edge cases I was missing.

Here's the new solution:

if len(xs) == 1:
    return str(xs[0])
p = []
n = []
for i in xs:
    if i < 0:
        n.append(i)
    elif i > 0:
        p.append(i)
if len(n) % 2 == 1:
    n.remove(max(n))
arr = p   n
if len(arr) == 0:
    return str(0)
v = 1
for j in arr:
    v *= j
return str(v)