python - Google Foobar 挑战 Power Hungry - 未通过测试。 5 个测试用例中的 3 个 [隐藏]？

Question

关闭。这个问题需要debugging details .它目前不接受答案。












想改进这个问题？将问题更新为 on-topic对于堆栈溢出。

1年前关闭。




Improve this question




我正在做谷歌 foobar 挑战，耗电。在隐藏的 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 指挥官的空间站很大。巨大的空间站需要很多能量。带有世界末日设备的巨大空间站需要更多的电力。为帮助满足空间站的电力需求，Lambda 指挥官在空间站外表面安装了太阳能电池板。但该站位于类星体量子通量场的中间，这对太阳能电池板造成了严重破坏。您和您的手下团队已被指派修理太阳能电池板，但您不能在不关闭空间站(以及所有那些讨厌的生命支持系统!)的情况下一次将它们全部拆除。

您需要弄清楚任何给定阵列中的哪些面板组可以脱机进行维修，同时仍保持每个阵列的最大功率输出，为此，您首先需要弄清楚每个阵列的最大输出是多少数组实际上是。编写一个函数 answer(xs)，它接受一个整数列表，表示数组中每个面板的功率输出水平，并返回这些数字的某个非空子集的最大乘积。因此，例如，如果一个数组包含功率输出水平为 [2, -3, 1, 0, -5] 的面板，则可以通过取子集找到最大乘积:xs[0] = 2, xs[1 ] = -3, xs[4] = -5，得到乘积 2*(-3)*(-5) = 30。所以 answer([2,-3,1,0,-5]) 将是“30"。

每个太阳能电池板阵列包含至少 1 个且不超过 50 个电池板，每个电池板将具有绝对值不大于 1000 的功率输出水平(有些电池板故障严重以至于它们正在消耗能量，但你知道面板波稳定器的一个技巧，可以让您组合两个负输出面板以产生其功率值倍数的正输出)。最终产品可能非常大，因此请以数字的字符串表示形式给出答案。

语言

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

测试用例

输入:(int list) xs = [2, 0, 2, 2, 0] 输出:(string) "8"

输入:(int list) xs = [-2, -3, 4, -5] 输出:(string) "60"

使用 verify [file] 来测试您的解决方案并查看它的效果。完成代码编辑后，使用 submit [file] 提交您的答案。如果您的解决方案通过了测试用例，它将从您的主文件夹中删除。

如果可能，请提出我在代码中的错误之处？谢谢。

Answer 1

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

Initial Algorithm

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

这个方法有 O(n) 复杂性(与发布方法的 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

战略

基于以下 facts 的算法代码:

如果有偶数个负数且没有零，则结果为
简单的产品

如果有奇数个负数且没有零，则结果为
除最大值负数外的所有乘积。

如果有零，结果是除这些零之外的所有乘积
一个异常(exception)情况。异常(exception)情况是当有一个
负数，所有其他元素为 0。在这种情况下，结果
为 0。

Alternate Algorithm

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 到 3 个产品对应于非空子序列。

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

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