目标
给你一个下标从 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。如果全是负数，初值设为第一个元素，之所以不设为1是因为如果只有一个负数，那么就应该取这个值，如果设为1后面再配对的话就不对了，所以需要特殊处理成对匹配的情况。
代码
/**
* @date 2024-09-03 8:57
*/
public class MaxStrength2708 {
public long maxStrength(int[] nums) {
long res = 1L;
Arrays.sort(nums);
int n = nums.length;
int i = n - 1;
for (; i >= 0; i--) {
if (nums[i] > 0) {
res *= nums[i];
} else if (nums[i] < 0) {
// 跳过0，使i指向最后一个负数
break;
}
}
int j = 0;
boolean flag = true;
// 至多一个负数，其余全是0，返回0。
if (i <= 0 && nums[n - 1] == 0) {
return 0L;
} else if (i == n - 1) {
// 如果全是负数
res = nums[0];
flag = false;
j = 1;
}
ArrayDeque<Integer> stack = new ArrayDeque<>();
for (; j <= i; j++) {
if (nums[j] < 0) {
if (stack.isEmpty() && flag) {
stack.push(nums[j]);
} else {
if (!flag) {
res *= nums[j];
} else {
res *= stack.pop() * nums[j];
}
flag = true;
}
}
}
return res;
}
}
性能
