Tìm tập hợp con của tập hợp các số nguyên có sản phẩm tối đa

Question

Đặt A là tập hợp số nguyên không trống. Viết hàm tìm kết quả là tập hợp con không trống của A có sản phẩm tối đa. Ví dụ: tìm ([- 1, -2, -3, 0, 2]) = 12 = (-2) * (- 3) * 2

Đây là những gì tôi nghĩ: chia danh sách thành danh sách các số nguyên dương và danh sách các số nguyên âm:

1. Nếu chúng tôi có số nguyên âm, nhân tất cả mọi thứ trong cả hai danh sách và chúng tôi có câu trả lời.
2. Nếu chúng tôi có một số lẻ các số nguyên âm, hãy tìm số nguyên lớn nhất và xóa số đó khỏi danh sách. Sau đó nhân tất cả mọi thứ trong cả hai danh sách.
3. Nếu danh sách chỉ có một phần tử, hãy trả lại phần tử này.

Dưới đây là mã của tôi bằng Python:

def find(xs): 
    neg_int = [] 
    pos_int = [] 
    if len(xs) == 1: 
     return str(xs[0]) 
    for i in xs: 
     if i < 0: 
      neg_int.append(i) 
     elif i > 0: 
      pos_int.append(i) 
    if len(neg_int) == 1 and len(pos_int) == 0 and 0 in xs: 
     return str(0) 
    if len(neg_int) == len(pos_int) == 0: 
     return str(0) 
    max = 1 
    if len(pos_int) > 0: 
     for x in pos_int: 
      max=x*max 
    if len(neg_int) % 2 == 1: 
     max_neg = neg_int[0] 
     for j in neg_int: 
      if j > max_neg: 
       max_neg = j 
     neg_int.remove(max_neg) 
    for k in neg_int: 
     max = k*max 
    return str(max) 

Tôi có thiếu gì không? P.S. Đây là một vấn đề từ thách thức foobar của Google, tôi dường như thiếu một trường hợp nhưng tôi không biết.

Bây giờ đây là vấn đề thực tế:

Answer 1

Dưới đây là một giải pháp mà không đòi hỏi các thư viện:

def find(l): 
    if len(l) <= 2 and 0 in l: # This is the missing case, try [-3,0], it should return 0 
     return max(l) 
    l = [e for e in l if e != 0] # remove 0s  
    r = 1 
    for e in l: # multiply all 
     r *= e 
    if r < 0: # if the result is negative, remove biggest negative number and retry 
     l.remove(max([e for e in l if e < 0])) 
     r = find(l) 
    return r 

print(find([-1, -2, -3, 0, 2])) # 12 
print(find([-3, 0])) # 0 

EDIT:

Tôi nghĩ rằng tôi đã tìm thấy những trường hợp còn thiếu đó là khi chỉ có hai yếu tố trong danh sách, và mức cao nhất là 0.

Answer 2

Bạn đơn giản hóa vấn đề này với reduce (trong functools trong Py3)

import functools as ft 
from operator import mul 

def find(ns): 
    if len(ns) == 1 or len(ns) == 2 and 0 in ns: 
     return str(max(ns)) 
    pos = filter(lambda x: x > 0, ns) 
    negs = sorted(filter(lambda x: x < 0, ns)) 
    return str(ft.reduce(mul, negs[:-1 if len(negs)%2 else None], 1) * ft.reduce(mul, pos, 1)) 

>>> find([-1, -2, -3, 0, 2]) 
'12' 
>>> find([-3, 0]) 
'0' 
>>> find([-1]) 
'-1' 
>>> find([]) 
'1' 

Answer 3

from functools import reduce 
from operator import mul 

def find(array): 
    negative = [] 
    positive = [] 
    zero = None 
    removed = None 

    def string_product(iterable): 
     return str(reduce(mul, iterable, 1)) 

    for number in array: 
     if number < 0: 
      negative.append(number) 
     elif number > 0: 
      positive.append(number) 
     else: 
      zero = str(number) 

    if negative: 
     if len(negative) % 2 == 0: 
      return string_product(negative + positive) 

     removed = max(negative) 

     negative.remove(removed) 

     if negative: 
      return string_product(negative + positive) 

    if positive: 
     return string_product(positive) 

    return zero or str(removed) 

Answer 4

Dưới đây là một giải pháp trong một vòng lặp:

def max_product(A): 
    """Calculate maximal product of elements of A""" 
    product = 1 
    greatest_negative = float("-inf") # greatest negative multiplicand so far 

    for x in A: 
     product = max(product, product*x, key=abs) 
     if x <= -1: 
      greatest_negative = max(x, greatest_negative) 

    return max(product, product // greatest_negative) 

assert max_product([2,3]) == 6 
assert max_product([-2,-3]) == 6 
assert max_product([-1, -2, -3, 0, 2]) == 12 
assert max_product([]) == 1 
assert max_product([-5]) == 1 

Tín dụng bổ sung: điều gì xảy ra nếu hạn chế số nguyên được giải phóng? Bạn cần thu thập thêm thông tin gì trong vòng lặp?