最大子集乘积算法挑战代码运行失败求助

挑战背景与任务 #

指挥官Lambda的空间站规模庞大，对能源需求极高，其外部安装的太阳能板因处于类星体量子通量场中出现故障。任务是找出可下线维修的太阳能板集合，同时维持阵列的最大功率输出，需先计算每个阵列的最大输出值。

需编写函数solution(xs)，接收一个整数列表（代表阵列中每个太阳能板的功率输出值），返回该列表某非空子集的最大乘积，最终结果以字符串形式返回（因乘积可能极大）。例如，输入[2, -3, 1, 0, -5]时，最大乘积为2*(-3)*(-5)=30，函数应返回"30"。

挑战规则 #

• 代码运行在Python 2.7.13沙箱中，通过调用solution()函数执行测试。
• 支持大部分标准库，但禁用bz2、crypt、fcntl等库。
• 禁止进行输入输出操作。

我的代码（运行失败） #

def solution(xs):
    # Define function multiply list together
    def get_product(numbers):
        total = 1
        for i in numbers:
            total *= i

        return total
    
    # Get list of combinations
    def get_possible_combinations(parent_list):
        def generate_combinations(subset, index, current_combination, result):
            if index == len(subset):
                result.append(current_combination)
                return
            generate_combinations(subset, index + 1, current_combination + [subset[index]], result)
            generate_combinations(subset, index + 1, current_combination, result)

        result = []
        generate_combinations(parent_list, 0, [], result)
        return result
    
    max_reached = 0
    possible_combinations = get_possible_combinations(xs)

    # Loop over all possible combinations
    for combination in possible_combinations:
        product = get_product(combination)
        
        if product > max_reached:
            max_reached = product

    return max_reached

代码问题分析与修复方案 #

核心问题1：性能爆炸 #

通过递归生成所有子集组合的方式，当输入列表长度超过20时，子集数量会达到2^20（约100万），更长的列表会直接超时甚至内存溢出，完全无法通过大规模测试用例。

核心问题2：边界情况处理错误 #

• 生成的子集包含空集，get_product([])返回1，但题目要求必须是非空子集，会干扰计算结果。
• 初始max_reached = 0，当所有元素都是负数（比如[-1, -2, -3]）或只有单个负数（比如[-5]）时，代码会错误返回0，违反非空子集的要求。

核心问题3：返回值类型不符合要求 #

题目要求返回字符串形式的结果，但代码返回整数，不仅无法处理极大乘积的溢出问题，也不满足格式要求。

修复后的代码 #

def solution(xs):
    if len(xs) == 1:
        return str(xs[0])
    
    positives = [num for num in xs if num > 0]
    negatives = [num for num in xs if num < 0]
    
    # 负数数量为奇数时，移除绝对值最小的负数（即最大的负数）
    if len(negatives) % 2 != 0:
        negatives.remove(max(negatives))
    
    total = 1
    # 计算所有有效元素的乘积
    for num in positives + negatives:
        total *= num
    
    # 处理无有效元素的情况（比如全零或负数移除后无剩余）
    if total == 1 and not positives and not negatives:
        return "0"
    
    return str(total)

修复说明 #

1. 单元素特殊处理：当列表只有一个元素时，直接返回该元素的字符串形式，满足非空要求。
2. 分类优化计算：将元素分为正数、负数两类，避免生成所有子集，时间复杂度降至O(n)。
3. 负数调整：如果负数数量为奇数，移除绝对值最小的负数，保证乘积最大化。
4. 边界兜底：当没有有效乘积组合时（比如全零），返回"0"。
5. 格式合规：最终结果转为字符串返回，满足题目对输出类型的要求。

内容的提问来源于stack exchange，提问作者umar mnaq