Ad-Hoc问题：乘积最大的子序列

摘要: 整数全选，负数选最小的偶数个，若除零外只有一个负数则答案为零

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，本文我们看一个常规的算法题。这也是一个 Ad-hoc 题，把问题分析清楚即可。

题目

给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, ... , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik] 。

请你返回老师创建的小组能得到的最大实力值为多少。

示例 1：
输入：nums = [3,-1,-5,2,5,-9]
输出：1350
解释：一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 (-5) 2 5 (-9) = 1350 ，这是可以得到的最大实力值。

示例 2：
输入：nums = [-4,-5,-4]
输出：20
解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。

提示：

1 <= nums.length <= 13
-9 <= nums[i] <= 9

题解

算法：分析问题

我们要从数组中选出若干个数，使得乘积最大。

对于一个正整数，选择它至少不会使得结果更坏，因此遇到正整数就直接选上即可。

对于负数来说，如果只有一个负数，那么能不选尽量不选；如果负数有两个以上，若有偶数个，则都选了；若有奇数个，则弃掉最大的那一个（离0最近的那个）其余的都选。

对于 0，只要选了，答案就是 0。因此只有当数组中有 0 ，且除了 0 以外只有一个负数的情况，才选 0。

综上，处理流程如下：

枚举数组中的各个数，维护以下信息：非零数字的乘积 total、最大的负数 max_nega、非零元素的个数 cnt、是否有 0 的标记 has_zero。

将所有非零的数字全都相乘，结果为 total，若 total 为正数，则它就是答案；若 total 为负数，说明有奇数个负数，此时要看非零元素个数 cnt，若 cnt > 1，则 total 除以最大的那个负数 max_nega，结果即为答案；若 cnt == 1，则要看是否有 0；若有零 has_zero，则答案为 0，否则为负数 total。

还有一种特殊情况，即数组中只有 0，此时 cnt == 0，答案返回零即可。

代码 (Python)

class Solution:
    def maxStrength(self, nums: List[int]) -> int:
        cnt = 0
        total = 1
        has_zero = False
        max_nega = -int(1e9)
        for x in nums:
            if x == 0:
                has_zero = True
            else:
                cnt += 1
                total *= x
                if x < 0:
                    max_nega = max(max_nega, x)
        if cnt == 0:
            return 0
        # cnt > 0
        if total > 0:
            return total
        # total < 0
        if cnt == 1:
            if has_zero:
                return 0
            else:
                return total
        return total // max_nega

---