Medium

题目描述

给你一个下标从 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] 的学生。强度为 (-4) * (-5) = 20。
我们无法获得更大的强度。

约束条件:

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

解题思路

这道题要求找到数组子集的最大乘积。由于数组长度较小（最多13个元素），可以考虑多种解法：

解法1：回溯枚举（推荐） 由于n≤13，可以枚举所有可能的子集（2^13 = 8192种），计算每个子集的乘积，找到最大值。这种方法简单直观，时间复杂度可接受。

解法2：贪心策略 根据数字的正负性分类处理：

  1. 所有正数都应该包含在结果中
  2. 负数成对出现时乘积为正，应该尽可能多地包含
  3. 如果负数个数为奇数，应该排除绝对值最小的负数
  4. 0的处理需要特别注意：当所有数都是负数且个数为奇数时，选择0比选择负数更好

解法3：动态规划 维护当前的最大值和最小值，因为负数乘以当前最小值可能得到更大的结果。

考虑到题目的数据规模和实现简单性，回溯枚举是最直接有效的方法。对于每个元素，我们有选择和不选择两种情况，递归处理所有可能性。

代码实现

class Solution {
public:
    long long maxStrength(vector<int>& nums) {
        int n = nums.size();
        long long maxVal = LLONG_MIN;
        
        // 枚举所有非空子集
        for (int mask = 1; mask < (1 << n); mask++) {
            long long product = 1;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    product *= nums[i];
                }
            }
            maxVal = max(maxVal, product);
        }
        
        return maxVal;
    }
};

class Solution:
    def maxStrength(self, nums: List[int]) -> int:
        n = len(nums)
        max_val = float('-inf')
        
        # 枚举所有非空子集
        for mask in range(1, 1 << n):
            product = 1
            for i in range(n):
                if mask & (1 << i):
                    product *= nums[i]
            max_val = max(max_val, product)
        
        return max_val

public class Solution {
    public long MaxStrength(int[] nums) {
        int n = nums.Length;
        long maxVal = long.MinValue;
        
        // 枚举所有非空子集
        for (int mask = 1; mask < (1 << n); mask++) {
            long product = 1;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    product *= nums[i];
                }
            }
            maxVal = Math.Max(maxVal, product);
        }
        
        return maxVal;
    }
}

var maxStrength = function(nums) {
    const n = nums.length;
    let maxVal = -Infinity;
    
    // 枚举所有非空子集
    for (let mask = 1; mask < (1 << n); mask++) {
        let product = 1;
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                product *= nums[i];
            }
        }
        maxVal = Math.max(maxVal, product);
    }
    
    return maxVal;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n × 2^n)，其中 n 是数组长度。需要枚举 2^n - 1 个非空子集，每个子集需要 O(n) 时间计算乘积
空间复杂度O(1)，只使用常数额外空间

相关题目