谷歌Foobar挑战力量饥饿-失败的测试第3号[隐藏]5个测试用例？

Question

我正在做谷歌足球挑战力量饥渴。我在5个隐藏的测试用例中有一个失败了。这是我的密码-

def answer(b):
from itertools import combinations
arr = []
for i in range(1,len(b)+1):
    comb = combinations(b,i)
    for j in list(comb):
        mul = 1
        for x in j:
            mul *= x
            if mul > 1000:
                break
            else:
                arr.append(mul)
return str(max(arr))

任务如下-

电源饥饿

拉姆达指挥官的空间站很大。巨大的空间站需要很大的能量。拥有末日设备的大型空间站需要更多的电力。为了满足空间站的电力需求，指挥官Lambda在空间站的外表面安装了太阳能电池板。但是空间站位于类星体量子通量场的中间，这对太阳能电池板造成了巨大的破坏。你和你的追随者小组被派去修理太阳能电池板，但你不可能在不关闭空间站(和所有那些讨厌的生命支持系统)的情况下立即把它们全部拆除。

您需要在任何给定数组中找出哪些面板集可以脱机修复，同时仍然保持每个数组的最大功率输出量，要做到这一点，首先需要确定每个数组的最大输出值是多少。编写一个函数答案(Xs)，它接受表示数组中每个面板的功率输出级别的整数列表，并返回这些数字的一些非空子集的最大乘积。例如，如果一个数组包含功率输出电平为2，-3，1，0，-5的面板，则通过取子集xs = 2，xs1 = -3，xs4 = -5，得到乘积2*(-3)*(-5) = 30。答案(2，-3,1,0，-5)是"30“。

每个太阳能电池板至少有一个，但不超过50个电池板，每个电池板的绝对值不超过1000 (一些电池板的故障严重到耗尽能量，但你知道太阳能电池板的波稳定器有一个诀窍，它可以让你把两个负输出板组合起来，产生其功率值倍数的正输出)。最终的产品可能很大，所以给出答案的字符串表示的数字。

语言

要提供Python解决方案，编辑solution.py以提供solution.java解决方案，编辑solution.java

测试用例

输入：(int列表) xs = 2，0，2，2，0输出：(字符串) "8“

输入：(int列表) xs = -2，-3，4，-5输出：(字符串) "60“

使用“验证文件”测试您的解决方案并查看它是如何实现的。编辑完代码后，使用submit文件提交答案。如果您的解决方案通过测试用例，它将从您的主文件夹中删除。

如果可能的话，请建议我在代码中错误的地方？谢谢。

Answer 1

您的当前算法不会扩展到处理50个面板，因为您必须生成所有2**50个子数组子集。

初始算法

来自https://www.geeksforgeeks.org/maximum-product-subset-array/

该方法具有O(n)复杂度(与posted方法的O(2^n)相比)。

from random import randint

def maxProductSubset(a, n): 
    if n == 1: 
        return a[0]  

    # Find count of negative numbers, count  
    # of zeros, maximum valued negative  
    # number and product of non-zero numbers  
    max_neg = -999999999999
    count_neg = 0
    count_zero = 0
    prod = 1
    for i in range(n): 

        # If number is 0, we don't  
        # multiply it with product.  
        if a[i] == 0:  
            count_zero += 1
            continue

        # Count negatives and keep  
        # track of maximum valued negative.  
        if a[i] < 0:  
            count_neg += 1
            max_neg = max(max_neg, a[i]) 

        prod = prod * a[i] 

    # If there are all zeros  
    if count_zero == n:  
        return 0

    # If there are odd number of  
    # negative numbers  
    if count_neg & 1:  

        # Exceptional case: There is only  
        # negative and all other are zeros  
        if (count_neg == 1 and count_zero > 0 and 
            count_zero + count_neg == n): 
            return 0

        # Otherwise result is product of  
        # all non-zeros divided by maximum  
        # valued negative.  
        prod = int(prod / max_neg) 

    return str(prod)  # Problem asks for string to be returned

# Test Code
if __name__ == '__main__': 
    big_array = [randint(-1000, 1000) for _ in range(51)]
    tests = [[-1], [-1, 0], [2, 0, 2, 2, 0],  [-2, -3, 4, -5], [ -1, -1, -2, 4, 3 ], big_array ]
    for t in tests:
        print('array {} \n\t max: {}'.format(t, maxProductSubset(t, len(t))))

输出

array [-1] 
     max: -1
array [-1, 0] 
     max: 0
array [2, 0, 2, 2, 0] 
     max: 8
array [-2, -3, 4, -5] 
     max: 60
array [-1, -1, -2, 4, 3] 
     max: 24
array [696, 254, 707, 730, 252, 144, 18, -678, 921, 681, -665, 421, -501, 204, 742, -609, 672, -72, 339, -555, -736, 230, -450, 375, 941, 50, 897, -192, -912, -915, 609, 100, -933, 458, -893, 932, -590, -209, 107, 473, -311, 73, 68, -229, 480, 41, -235, 558, -615, -289, -643] 
     max: 112783193423281396421025291063982496313759557506029207349556366834514274891010648892576460433185005069070271452630069726538629120

战略

基于以下事实的算法代码

1. 如果有偶数的负数而没有零，则结果只是所有的乘积。
2. 如果有奇数的负数而没有零，则结果是除最大值负数外的所有结果的乘积。
3. 如果存在零，则结果是除这些零外的所有结果的乘积，只有一个例外情况。例外情况是有一个负数，而所有其他元素都是0。在这种情况下，结果是0。

交替算法

from functools import reduce
from itertools import combinations
from random import randint

def answer(a, n):
    def prod(arr):
        " Multiply elements of array "
        return reduce((lambda x, y: x * y), arr, 1)

    def max_single_sign_prod(arr):
        " Find max product of array assuming all element are same sign "
        if arr[0] == 0:
            return 0  # all zero
        if arr[0] > 0:
            return proc(arr) # all positive

        # all negative
        p = prod(arr)
        if len(arr) > 1 and len(arr) % 2:
            return p // max(arr)
        else:
            return p

    # Generate all positive, all negative and all zero sublists of arr
    pos = [i for i in a if i > 0]
    neg = [i for i in a if i < 0]
    zeros = [i for i in a if i == 0]

    # Find non-empty sublists
    b = [x for x in [pos, neg, zero] if len(x) > 0]

    products = list(map(max_single_sign_prod, b))

    # Find optimal combinations of these product to product max
    # There's only 3**2 or 9 combinations to try
    max_product = max(prod(c) for c in list(comb) for comb in combinations(products, i) for i in range(len(b)+1))

    return str(max_product)

if __name__ == '__main__': 
    big_array = [randint(-1000, 1000) for _ in range(51)]
    tests = [[-1], [1], [-1, 0], [2, 0, 2, 2, 0],  [-2, -3, 4, -5], [ -1, -1, -2, 4, 3 ], big_array ]
    for t in tests:
        print('array {} \n\t max: {}'.format(t, maxProductSubset(t, len(t))))

战略

我们从数组中生成三个子序列：

1. 全正数
2. 所有零元素
3. 所有负元素

每个序列的最大乘积如下：

• 所有正数--所有数字的乘积
• 所有零--零
• 所有负数--所有数的乘积(对于偶数长度)，否则除以最大乘积(如果是奇数长度)。

我们计算每个非空序列(即所有正、零和负)的最大乘积。

这导致与非空子序列对应的1到3个乘积。

我们的答案是找到提供最大价值的1到3产品的组合。

最多有3**2组合，因此这是很容易计算的。

Answer 2

所以，我想出了解决方案，它解决了我所有的测试用例。一种非常规的解决方案：

• 首先，检查数组是否有所有零，在这种情况下返回0。
• 接下来，检查是否只有一个元素，并且它是负数，返回这个数字。
• 接下来，检查是否只有一个负数，其余的为零，在这种情况下返回零。

这是程序中唯一的例外情况。

接下来的步骤很简单：

• 找出所有非零数的乘积。
• 如果产品为正，则返回该数字，因为它是最大的可能值。
• 如果产品是负数，除以最小负数，并返回答案！ def解( xs )：if(xs.count(0) == len( xs ))：返回(str( 0) ) if(len(xs) == 1和len(n在xs中为n，如果n< 0) == 1)：返回(str(Xs)) if ( in (n in xs，n<0) == 1和xs.count(0) == len(xs)-1)：返回(str(0))如果(i =0和i <= 1000)：Val *= i如果Val < 0: BigNeg = max(n在xs中n为n，n< 0) Val = Val/BigNeg返回(str(int( Val )

Answer 3

野蛮的强迫这是不可侵犯的。任何尺寸的50个项目的组合( r )都是巨大的。

考虑一下，如果你的最后选择中有一个偶数的负数，你就会得到一个净的正结果。选择列表中的所有正数，然后在列表中选择最小(绝对值最大) k负数，其中k % 2 == 0 ( k为偶数)，k尽可能大。

不同的说法，

1. 把所有的正数都拿出来。我们喜欢正面数字，它们总是帮助我们。
2. 把所有的负数取下来。
3. 如果你有一个奇数的负数，省略一个最大的数值(最接近于零)。
4. 在第三步之后，取你所取数字的乘积，并返回它。

正如Simon提到的，只有一个负数是有边的。我们能做的就是把它还回去。同样，对于没有正数、单个负数和一个或多个零的情况，返回0。