2708. 一个小组的最大实力值

题目描述：

给你一个下标从 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

---

解题分析及思路：

方法：排序＋枚举

思路：

首先对数组进行排序，然后枚举所有可能的组合，计算乘积，并记录最大的乘积。

通过正数、负数、零的个数，来确定最终的组合。

• 如果数组中只有1个元素，直接返回该元素（需保证数组非空）。
• 如果数组中只有2个以上元素
  • 正数个数为0，负数不多于1个，零的个数大于等于1，则返回0。
  • 当正数或负数个数大于0，零个数为0
    • 负数个数为奇数，结果移除最大的负数。
    • 否则，返回乘积。

func maxStrength(nums []int) int64 {
	if len(nums) == 1 {
		return int64(nums[0])
	}
	sort.Ints(nums)
	var neg, pos, zero int
	var res int = 1
	var negMax int = -10
	for _, num := range nums {
		if num < 0 {
			res *= num
			neg++
			if num > negMax {
				negMax = num
			}
		} else if num > 0 {
			res *= num
			pos++
		} else {
			zero++
		}
	}
	if pos == 0 && neg <= 1 && zero != 0 {
		return 0
	}
	if neg%2 == 1 {
		return int64(res / negMax)
	}
	return int64(res)
}

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:8 ms,击败了35.71% 的Go用户
• 内存消耗:2.8 MB,击败了78.57% 的Go用户