class Solution {
public:
long long maxStrength(vector<int>& nums) {
}
};
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] 输出：20 解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。
提示：
1 <= nums.length <= 13-9 <= nums[i] <= 9原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2024-09-03 09:29:56
impl Solution {
pub fn max_strength(nums: Vec<i32>) -> i64 {
let mut mn = nums[0] as i64;
let mut mx = mn;
for &x in &nums[1..] {
let x = x as i64;
let tmp = mn;
mn = mn.min(x).min(mn * x).min(mx * x);
mx = mx.max(x).max(tmp * x).max(mx * x);
}
mx
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.8 MB, 提交时间: 2024-09-03 09:29:21
func maxStrength(nums []int) int64 {
mn, mx := nums[0], nums[0]
for _, x := range nums[1:] {
mn, mx = min(mn, x, mn*x, mx*x),
max(mx, x, mn*x, mx*x)
}
return int64(mx)
}
python3 解法, 执行用时: 3060 ms, 内存消耗: 15.9 MB, 提交时间: 2023-05-28 10:36:21
class Solution:
def maxStrength(self, nums: List[int]) -> int:
n = len(nums)
a = max(nums)
for mask in range(1, 1 << n):
b = 1
for i in range(n):
if mask >> i & 1:
b *= nums[i]
a = max(a, b)
return a
python3 解法, 执行用时: 40 ms, 内存消耗: 16.1 MB, 提交时间: 2023-05-28 10:36:14
class Solution:
def maxStrength(self, nums: List[int]) -> int:
nums.sort()
i = bisect_left(nums, 0)
i -= i & 1
j = bisect_right(nums,0)
n = len(nums)
if j == n and i == 0:
return nums[-1]
return reduce(lambda x, y: x * y, nums[:i] + nums[j:])
java 解法, 执行用时: 2 ms, 内存消耗: 41.9 MB, 提交时间: 2023-05-28 10:35:16
class Solution {
public long maxStrength(int[] nums) {
long res = 1;
Arrays.sort(nums);
int n = nums.length;
for(int i = 0; i < n; i+=2){
if(i < n-1 && nums[i] < 0 && nums[i+1] < 0){
res = res * nums[i] * nums[i+1];
}else{
break;
}
}
for(int i = n-1; i >= 0; i--){
if(nums[i] > 0){
res *= nums[i];
}
}
//必选一个，选最大
if(res == 1){
return nums[n-1];
}
return res;
}
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 45.4 MB, 提交时间: 2023-05-28 10:34:34
/**
* 先从小到大排序;
* 选所有的正数, 或偶数个负数;
*/
class Solution {
public:
long long maxStrength(vector<int>& nums) {
sort(nums.begin(), nums.end());
long long ans = 1;
int n = nums.size();
int cnt = 0;
for (int i = 0; i < n; i++) {
/* 当前乘积为正, 或者下个乘数为负 */
if (ans * nums[i] > 0 || (i + 1 < n && nums[i + 1] < 0)) {
ans *= nums[i];
cnt++;
}
}
return cnt > 0 ? ans : nums[n - 1];
}
};
python3 解法, 执行用时: 56 ms, 内存消耗: 16.1 MB, 提交时间: 2023-05-28 10:34:02
class Solution:
def maxStrength(self, nums: List[int]) -> int:
if len(nums)==1: return nums[0] # 特判只有1个元素，除此外答案不可能是负数
pos = [num for num in nums if num>0]
neg = [num for num in nums if num<0]
if not pos:
return reduce(lambda x,y:x*y,neg)//(max(neg)**(len(neg)%2)) if len(neg)>=2 else 0 #这个表达式整合了奇数（不小于3）和偶数（不小于2）个负数，0或1个负数则不选负数。注意只要数组元素不止1个，答案最小也是0
ans = reduce(lambda x,y:x*y,pos)
return ans*reduce(lambda x,y:x*y,neg)//(max(neg)**(len(neg)%2)) if len(neg)>=2 else ans
javascript 解法, 执行用时: 104 ms, 内存消耗: 44.8 MB, 提交时间: 2023-05-28 10:32:58
/**
* @param {number[]} nums
* @return {number}
* 每一轮都把最大最小值求出来(最小值遇到负数时能变成最大值)，遍历一次更新最大最小值
*/
var maxStrength = function(nums) {
let max = nums[0];
let min = nums[0];
let res = nums[0];
for (let i = 1; i < nums.length; i++) {
let temp = max;
max = Math.max(max * nums[i], min * nums[i], nums[i], max);
min = Math.min(temp * nums[i], min * nums[i], nums[i], min);
}
return Math.max(res, max);
};