首页算法

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

难度中等

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

解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。

提示：

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

# 子集型回溯

要么选，要么不选

class Solution {
    public long maxStrength(int[] nums) {
        this.nums = nums;
        dfs(0, 1, 0);
        return ans;
    }
    int[] nums;
    long ans = Integer.MIN_VALUE;
    
    //[正数，负数]
    public void dfs(int i, long mul, int cnt) {
        int n = nums.length;
        if (i == n) {
            // 必须选
            if (cnt != 0) {
                ans = Math.max(ans, mul);
            }
            return;
        }
        // 选或者不选
        dfs(i + 1, mul * nums[i], cnt + 1);
        dfs(i + 1, mul, cnt);
    }
}
# 动态规划


dp1dp1 表示前 ii 个数正数的最大值，dp2dp2 表示前 ii 个数负数的最小值


dp1=max(dp1,nums[i],dp1[i−1]×nums[i],dp2[i−1]×nums[i])dp1 = max(dp1,nums[i],dp1[i-1]\times nums[i],dp2[i-1]\times nums[i])


    

  • 

    （前一个数作为最大值，当前数作为最大值，i−1i - 1 个数的正数最大值 ×\times nums[i]nums[i]，i−1i - 1 个数的负数最小值 ×\times nums[i]nums[i]）
    

    i−1i - 1 个数的负数最小值 ×\times nums[i]nums[i]：由于当前数可能是负数，负数乘以负数为正数
    

    当前数作为最大值：由于 dp1dp1 可能为负数
    

    • 



dp2=min(dp2,nums[i],dp1[i−1]×nums[i],dp2[i−1]×nums[i])dp2 = min(dp2,nums[i],dp1[i-1]\times nums[i],dp2[i-1]\times nums[i])


class Solution {
    public long maxStrength(int[] nums) {
        int n = nums.length;
        long mx = nums[0];
        long mn = nums[0];
        for (int i = 1; i < n; i++) {
            long t = mx;
            mx = Math.max(Math.max(mx, nums[i]), Math.max(mx * nums[i], mn * nums[i]));
            mn = Math.min(Math.min(mn, nums[i]), Math.min(t * nums[i], mn * nums[i]));
        }
        return mx;
    }
}
# 贪心 + 排序


由于要让实力值最大，所以首先把所有为正数的相乘即可。


若含有负数，需要保证负数个数大于 11，最后结果集只需要偶数个即可


对于 [−9,0][-9,0]，−9-9


排序之后只需要判断负数个数 <=1<=1 并且 nums[n−1]<=0nums[n - 1] <= 0




即：最多只有两个元素，要么一个负数要么 0 搭配一个负数




class Solution {
    public long maxStrength(int[] nums) {
        int n = nums.length;
        long ans = 1;
        boolean f = false;
        for (int num : nums) {
            if (num > 0) {
                f = true;
                ans *= num;
            }
        }
        Arrays.sort(nums);
        int prev = 10;
        int cnt = 0;
        for (int num : nums) {
            if (num >= 0) {
                break;
            }
            cnt++;
            prev = num;
            ans *= num;
        }
        // 最多只有两个元素，要么一个负数要么 0 搭配一个负数
        if (cnt <= 1 && nums[n - 1] <= 0) {
            return nums[n - 1];
        }
        if (cnt % 2 == 1) {
            ans /= prev;
        }
        return ans;
    }
}