一个小组的最大实力值
难度:
标签:
题目描述
You are given a 0-indexed integer array nums representing the score of students in an exam. The teacher would like to form one non-empty group of students with maximal strength, where the strength of a group of students of indices i0, i1, i2, ... , ik is defined as nums[i0] * nums[i1] * nums[i2] * ... * nums[ik].
Return the maximum strength of a group the teacher can create.
Example 1:
Input: nums = [3,-1,-5,2,5,-9] Output: 1350 Explanation: One way to form a group of maximal strength is to group the students at indices [0,2,3,4,5]. Their strength is 3 * (-5) * 2 * 5 * (-9) = 1350, which we can show is optimal.
Example 2:
Input: nums = [-4,-5,-4] Output: 20 Explanation: Group the students at indices [0, 1] . Then, we’ll have a resulting strength of 20. We cannot achieve greater strength.
Constraints:
1 <= nums.length <= 13-9 <= nums[i] <= 9
代码结果
运行时间: 24 ms, 内存: 16.0 MB
/*
* 思路：
* 使用 Java Streams 处理数组。
* 由于 Streams 不支持原生的组合生成，需要手动实现。
* 我们将所有组合的结果收集到一个列表中，然后返回最大值。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
import java.util.List;
import java.util.stream.Collectors;
public class MaxStrengthStream {
public static int maxStrength(int[] nums) {
int n = nums.length;
List<Integer> products = IntStream.range(1, 1 << n) // 避免空集
.mapToObj(i -> IntStream.range(0, n)
.filter(j -> (i & (1 << j)) != 0)
.map(j -> nums[j])
.reduce(1, (a, b) -> a * b)
)
.collect(Collectors.toList());
return products.stream().max(Integer::compare).orElse(Integer.MIN_VALUE);
}
public static void main(String[] args) {
int[] nums1 = {3, -1, -5, 2, 5, -9};
int[] nums2 = {-4, -5, -4};
System.out.println(maxStrength(nums1)); // 输出 1350
System.out.println(maxStrength(nums2)); // 输出 20
}
}解释
方法:
此题解采用动态规划的方法来解决问题。定义两个变量 dpMin 和 dpMax 分别存储当前遍历到的元素之前的最小乘积和最大乘积。初始化这两个变量为数组的第一个元素。随后，对数组中的每一个元素进行遍历，计算与当前元素相乘后可能得到的新的最小乘积和最大乘积。这一步是通过比较当前最大最小乘积与当前元素相乘的结果，以及当前元素本身来确定。每次遍历更新结果的最大值，即可能的最大实力值。这种方法有效处理了负数乘积变正数的情况，从而确保能找到真正的最大乘积。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在动态规划解法中，需要同时维护最小乘积和最大乘积的状态？
▷🦆
在更新最大乘积和最小乘积时，为什么要将当前元素单独考虑，即为什么要包括`x`在内比较？
▷🦆
在计算新的最小乘积和最大乘积时，为什么要使用临时变量ndpMin和ndpMax进行更新？直接更新dpMin和dpMax是否会有问题？
▷🦆
如果数组中包含0，这种算法如何处理？0会对最大实力值的计算产生什么影响？
▷